面试题 22-easy-链表中倒数第k个节点

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

/

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

内存虽然只击败了14.67%用户，但是大家性能基本也差不到哪里去

这道题在解题思想上还是比较简单的，使用快慢指针法就能轻易解决，但是比较小坑的是，边界值问题：
快指针需要走到链表末尾最后一个值 nil

 // 快慢指针法
func getKthFromEnd(head *ListNode, k int) *ListNode {
   left,right := head,head

   for right!= nil{
       right = right.Next
       if k==0{
           left = left.Next
       }else {
           k--
       }
   }
   return left
}

附录：
大神写法： 虽然我感觉还没有我的思路清晰

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getKthFromEnd(head *ListNode, k int) *ListNode {
    p1, p2 := head, head
    if k < 1 {return nil}
    for i := 0; i < k; i++ {
        if p2 == nil {return nil}
        p2 = p2.Next
    }

    for p2 != nil {
        p2 = p2.Next
        p1 = p1.Next
    }

    return p1
}