链表一些算法技巧&模版总结

1.翻转链表

可以使用哑结点的技巧

中心思想是：

1）创建哑结点new ListNode(0);
2）遍历head，每次遍历，将哑结点的next先保存下来
3）将哑结点的next指向目前遍历到的head值的节点
4）再将这次遍历临时保存下来的哑结点的next节点，重新连接到哑结点的m.next.next = temp
5）直到head为null，遍历完成，m.next即为翻转后的链表

图解.png

模版代码为：

   /**
     * 翻转链表 
     */
    public ListNode revListNode(ListNode head) {
        // 创建哑结点
        ListNode m = new ListNode(0);
        ListNode temp = null;
        while (head != null) {
            // 遍历head，每次遍历，将哑结点的next先保存下来
            temp = m.next;
            // 将哑结点的next指向目前遍历到的head值的节点
            m.next = new ListNode(head.val);
            head = head.next;
            // 再将这次遍历临时保存下来的哑结点的next节点，重新连接到哑结点的m.next.next = temp
            m.next.next = temp;
        }
        // 直到head为null，遍历完成，m.next即为翻转后的链表
        return m.next;
    }

2.求取链表中的倒数节点

可以使用快慢指针的方法

中心思想是：

1）双指针移动，初始都指向head
2）先将p1移动k位
3）然后才开始移动p2，同时继续移动p1
4）直到p1指向末尾，那么p2将会移动L-k个位置，那么p2此时指向为倒数第k个节点

图解.png

模版代码为：

    /**
     * 快慢指针找到链表的倒数k节点
     */
    public ListNode getNthKNode(ListNode head, int k) {
        ListNode p1 = head, p2 = head;
        while (p1 != null) {
            p1 = p1.next;
            if (k < 1) {
                p2 = p2.next;
            }
            k--;
        }
        return p2;
    }