链表之双指针

什么是链表

链表是一种数据结构， 包含存储的值和指向一个节点的指针，且是单向的。 我们要去查找某个值，需要从头节点开始，往后遍历，所以时间复杂度为O（n）。

注意

切记一般在有关链表的题目，都需要建立虚拟头节点，一个甚至多个。

经典题目

1. 给定一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
   

   输入：head = [1,2,3,4,5], n = 2
   输出：[1,2,3,5]

   分析：拿到这道题，第一想法就是从头节点开始遍历，记录链表节点的个数为LN， 然后再重新从头节点遍历一次，并同时计数，当遍历到Ln - n + 1的时候，这个节点就是我们要删除的节点，然后将第Ln -n的这个节点的Next指向Ln - n + 1节点的下一个节点，这种做法可行，不过需要遍历两次。 我们能不能做到只遍历一次， 就可以完成节点删除来，答案是可以的。 这里面需要，定义两个指针，一个指针先行，另一个指针后行， 让后一个去追前一个，可以理解为快慢指针的方式。 先让第一个指针走n步， 然后两个指针再同时走完， 必然第一个指针会先走到最后一个节点，这个时候会发现第二个指针恰好走到倒数第n+1个节点，恰恰还有n个点没有走，这个时候就可以进行指针重新指向，删除倒数第n个节点，这么一想来，方法好极了，很巧妙，只需要遍历一次即可。
   代码实现：

   func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{0, head}
    firstNode := head
    secondNode := dummy
    for iii := 0; iii < n; iii++{
        firstNode = firstNode.Next
    }
    for firstNode != nil {
        firstNode = firstNode.Next
        secondNode = secondNode.Next
    }
    secondNode.Next = secondNode.Next.Next
    return dummy.Next
   }

总结

双指针法可以节点链表大部分算法题，而且高效。