Java&Go-剑指Offer面试题22：链表中倒数第k个结点-双指针

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

• 算法
  • 1.在头节点前面建立伪节点
  • 2.双指针，前指针先走到第k个节点，随后前后指针一起走，当前指针走到结尾null节点时，后指针即指向倒数第k个节点

public ListNode getKthFromEnd(ListNode head, int k) {
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    ListNode before = dummy;
    while (k-- > 0) {
        before = before.next;
        if (before == null) {
            return null;
        }
    }
    ListNode behind = dummy;
    while (before != null) {
        before = before.next;
        behind = behind.next;
    }
    return behind;
}

func getKthFromEnd(head *ListNode, k int) *ListNode {
    var dummy = ListNode{-1, head}
    var before = &dummy
    for k > 0 {
        before = before.Next
        if before == nil {
            return nil            
        }
        k--
    }
    var behind = &dummy
    for before != nil {
        behind = behind.Next
        before = before.Next
    }
    return behind
}