剑指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