剑指 Offer 22. 链表中倒数第k个节点

题目

剑指 Offer 22. 链表中倒数第k个节点

我的复述：
假如有一个链表为：1->2->3->4->5->6，输入的k=2，则输出为该链表倒数第2个节点，也就是正数第5个节点5。

题解

双指针

• 新建latter和former两个快慢双指针；
• 先将former指针向前移动k个长度；
• 再同时将latter和former指针向链表尾部移动；
• 当former指针指向为null时，此时latter指针指向的就是要返回的值。

//Java
/**
 * 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) {
        //初始化两个指针 former和latter，一开始都指向链表的头节点
        //指针former指向链表的头节点
        ListNode former = head;
        //指针latter指向列表的头结点
        ListNode latter = head;
        //让former指针先向前走k步
        for (int i = 0;i < k;i++) {
            former = former.next;
        }
        //让这两个指针former和latter同时向前移动，直到后指针former指向NULL
        while (former != null) {
            former = former.next;
            latter = latter.next;
        }
        return latter;
    }
}

//Go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getKthFromEnd(head *ListNode, k int) *ListNode {
    //初始化两个指针 former和latter，一开始都指向链表的头节点
    //指针former指向链表的头节点
    former := head
    //指针latter指向列表的头结点
    latter := head
    //让former指针先向前走k步
    for i := 0;i < k;i++ {
        former = former.Next
    }
    //让这两个指针former和latter同时向前移动，直到后指针former指向NULL
    for former != nil {
        former = former.Next
        latter = latter.Next
    }
    return latter
}