剑指offer：22-25记录

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。

示例：

给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

思路：快指针先走k步，然后快慢指针一起走到快指针到头为止，这时慢指针就是答案。

  

   

    

     

    
    

     

      /**
     
    
   

    

     

    
    

     

       * Definition for singly-linked list.
     
    
   

    

     

    
    

     

       * public class ListNode {
     
    
   

    

     

    
    

     

       * int val;
     
    
   

    

     

    
    

     

       * ListNode next;
     
    
   

    

     

    
    

     

       * ListNode(int x) { val = x; }
     
    
   

    

     

    
    

     

       * }
     
    
   

    

     

    
    

     

       */
     
    
   

    

     

    
    

     

      class Solution {
     
    
   

    

     

    
    

     
 public ListNode getKthFromEnd(ListNode head, int k) {
     
    
   

    

     

    
    

     

       ListNode former = head, latter = head;
     
    
   

    

     

    
    

     
 for(int i = 0; i < k; i++)
     
    
   

    

     

    
    

     

       former = former.next;
     
    
   

    

     

    
    

     
 while(former != null) {
     
    
   

    

     

    
    

     

       former = former.next;
     
    
   

    

     

    
    

     

       latter = latter.next;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return latter;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
  
 

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
 

限制：

0 <= 节点个数 <= 5000

  

   

    

     

    
    

     

      /**
     
    
   

    

     

    
    

     

       * Definition for singly-linked list.
     
    
   

    

     

    
    

     

       * public class ListNode {
     
    
   

    

     

    
    

     

       * int val;
     
    
   

    

     

    
    

     

       * ListNode next;
     
    
   

    

     

    
    

     

       * ListNode(int x) { val = x; }
     
    
   

    

     

    
    

     

       * }
     
    
   

    

     

    
    

     

       */
     
    
   

    

     

    
    

     

      class Solution {
     
    
   

    

     

    
    

     
	public ListNode reverseList(ListNode head) {
     
    
   

    

     

    
    

     
 //前一个节点
     
    
   

    

     

    
    

     

      		ListNode pre = null;
     
    
   

    

     

    
    

     
 //当前处理节点
     
    
   

    

     

    
    

     

      		ListNode cur = head;
     
    
   

    

     

    
    

     
 //记录后一个节点用
     
    
   

    

     

    
    

     

      		ListNode tmp = null;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
		while(cur!=null) {
     
    
   

    

     

    
    

     
			//记录当前节点的下一个节点
     
    
   

    

     

    
    

     

      			tmp = cur.next;
     
    
   

    

     

    
    

     
			//然后将当前节点指向pre
     
    
   

    

     

    
    

     

      			cur.next = pre;
     
    
   

    

     

    
    

     
			//pre和cur节点都前进一位
     
    
   

    

     

    
    

     

      			pre = cur;
     
    
   

    

     

    
    

     

      			cur = tmp;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		return pre;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      }
     
    
  
 

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
限制：

0 <= 链表长度 <= 1000

思路：链表的一次归并。思路和数组类似。

  

   

    

     

    
    

     

      /**
     
    
   

    

     

    
    

     

       * Definition for singly-linked list.
     
    
   

    

     

    
    

     

       * public class ListNode {
     
    
   

    

     

    
    

     

       * int val;
     
    
   

    

     

    
    

     

       * ListNode next;
     
    
   

    

     

    
    

     

       * ListNode(int x) { val = x; }
     
    
   

    

     

    
    

     

       * }
     
    
   

    

     

    
    

     

       */
     
    
   

    

     

    
    

     

      class Solution {
     
    
   

    

     

    
    

     
 public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
     
    
   

    

     

    
    

     

       ListNode ans=new ListNode(-1);
     
    
   

    

     

    
    

     

       ListNode temp=ans;
     
    
   

    

     

    
    

     
 while(l1!=null && l2!=null){
     
    
   

    

     

    
    

     
 if(l1.val>l2.val){
     
    
   

    

     

    
    

     

       ans.next=l2;
     
    
   

    

     

    
    

     

       l2=l2.next;
     
    
   

    

     

    
    

     

       }else{
     
    
   

    

     

    
    

     

       ans.next=l1;
     
    
   

    

     

    
    

     

       l1=l1.next;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       ans=ans.next;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if(l1!=null)ans.next=l1;
     
    
   

    

     

    
    

     
 if(l2!=null)ans.next=l2;
     
    
   

    

     

    
    

     
 return temp.next;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/104758590