双指针法

在数组的时候使用过双指针法，在对链表进行操作的时候，双指针法依旧可以使用在对链表遍历的操作。

反转链表

题目描述：

力扣链接🔗

题目分析：

如果再定义一个新的链表，实现链表元素的反转，其实这是对内存空间的浪费。其实只需要改变链表的next指针的指向，直接将链表反转 ，而不用重新定义一个新的链表，如图所示:

之前链表的头节点是元素1， 反转之后头结点就是元素5 ，这里并没有添加或者删除节点，仅仅是改变next指针的方向。

步骤：

首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null。

然后就要开始反转了，首先要把 cur->next 节点用tmp指针保存一下，也就是保存一下这个节点。

为什么要保存一下这个节点呢，因为接下来要改变 cur->next 的指向了，将cur->next 指向pre ，此时已经反转了第一个节点了。

接下来，就是循环走如下代码逻辑了，继续移动pre和cur指针。

最后，cur 指针已经指向了null，循环结束，链表也反转完毕了。 此时我们return pre指针就可以了，pre指针就指向了新的头结点。

代码：

解法一：

/**
 *  双指针法
 * @param head
 * @return
 */
public ListNode reverseList(ListNode head) {
    ListNode pre = null;
    ListNode cur = head;
    ListNode tmp = null;  // 临时节点保存cur下一个节点，防止指针指向反转后找不到下一个节点
    while (cur != null) {
        tmp = cur.next;
        cur.next = pre;
        // 向后移动
        pre = cur;
        cur = tmp;
    }
    return pre;
}

解法二：递归法（详细见递归）

两两交换链表中的节点

题目描述：

力扣链接🔗

题目分析：

建议使用虚拟头结点，这样会方便很多，要不然每次针对头结点（没有前一个指针指向头结点），还要单独处理。

代码：

解法一：虚拟头结点 + 双指针法

    /**
     *  虚拟头节点法
     * @param head
     * @return
     */
public ListNode swapPairs(ListNode head) {
    // 虚拟头节点
    ListNode dummyNode = new ListNode(0);
    dummyNode.next = head;
    ListNode pre = dummyNode;
    ListNode tmp = null;    // 临时节点
    // 注意判断只有一个节点的情况，所以head.next也需要判断
    // 也可以使用pre.next != null && pre.next.next != null判断
    while (head != null && head.next != null) {
        tmp = head.next.next;
        pre.next = head.next;
        head.next.next = head;
        head.next = tmp;
        // 向后移动
        pre = head;
        head = tmp;
    }
    return dummyNode.next;
}

解法二：递归法（详细见递归）

链表相交

题目描述：

力扣链接🔗

题目分析：

简单来说，就是求两个链表交点节点的指针。 这里同学们要注意，交点不是数值相等，而是指针相等。
为了方便举例，假设节点元素数值相等，则节点指针相等。
看如下两个链表，目前curA指向链表A的头结点，curB指向链表B的头结点：

我们求出两个链表的长度，并求出两个链表长度的差值，然后让curA移动到，和curB 末尾对齐的位置，如图：

此时我们就可以比较curA和curB是否相同，如果不相同，同时向后移动curA和curB，如果遇到curA == curB，则找到交点。否则循环退出返回空指针。

代码：

解法一：

public class Solution {
        /**
         * 优化方法
         *
         * @param headA
         * @param headB
         * @return
         */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA;
        ListNode curB = headB;
        int lenA = 0, lenB = 0;
        // 分別计算两个链表的长度
        while (curA != null) {
            curA = curA.next;
            lenA++;
        }
        while (curB != null) {
            curB = curB.next;
            lenB++;
        }
        curA = headA;
        curB = headB;
        // 让curA为最长链表的头
        if (lenA < lenB) {
            int tmpLen = lenA;
            lenA = lenB;
            lenB = tmpLen;
            // 交换指针
            ListNode tmpNode = curA;
            curA = curB;
            curB = tmpNode;
        }
        // 将长的链表移动到和短的链表尾部平齐
        int count = lenA - lenB;
        while (count-- > 0) {
            curA = curA.next;
        } 
        // 进行比较，相等则返回，此时长度相同
        while (curA != null) {
            if (curA == curB) {
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        return null;
        }
}

解法二：

public class Solution {
    /**
         * 循环遍历(时间复杂度为O（n的平方）)
         * @param headA
         * @param headB
         * @return
         */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode curA = headA;
        ListNode curB = headB;
        // 循环判断
        while (curA != null) {
            while (curB != null) {
                if (curA == curB)
                    return curA;
                curB = curB.next;
            }
            curA = curA.next;
            curB = headB;
        }
        return null;
    }  
}

解法三：

// 双指针法
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB ==null) return null;
    ListNode nodeA = headA, nodeB = headB;
    while (nodeA != nodeB) {
        // 移动到尾部之后，在移动到另一个节点的头节点点
        nodeA = nodeA == null ? headB : nodeA.next;
        nodeB = nodeB == null ? headA : nodeB.next;
    }
    return nodeA;
}

环形链表Ⅱ

题目描述：

力扣链接🔗

题目解析：

详细解析🔗

代码：

解法一：在查重的情况下可以考虑hash表。

public class Solution {
    /**
         * 哈希表
         *
         * @param head
         * @return
         */
    public ListNode detectCycle(ListNode head) {
        HashSet<ListNode> set = new HashSet<ListNode>();
        ListNode cur = head;
        while (cur != null) {
            if (set.contains(cur)) {
                return cur;
            }
            set.add(cur);
            cur = cur.next;
        }
        return null;
    }
}

解法二：

public class Solution {
    /**
         * 快慢指针法
         *
         * @param head
         * @return
         */
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        // 判断为null或者一个节点时
        while (fast != null && fast.next != null) {
            // fast移动两步，slow移动一步
            slow = slow.next;
            fast = fast.next.next;
            // 在环中相交时
            if (slow == fast) {
                ListNode index1 = slow;
                ListNode index2 = head;
                while (index1 != index2) {
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
            }
        }
        return null;
    }
}

删除链表的倒数第N个节点

题目描述

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
进阶：你能尝试使用一趟扫描实现吗？
示例 1：

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

思路

双指针的经典应用，如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了。
思路是这样的，但要注意一些细节。
分为如下几步：

• 首先这里我推荐大家使用虚拟头结点，这样方面处理删除实际头结点的逻辑。
• 定义fast指针和slow指针，初始值为虚拟头结点，如图：

• fast首先走n + 1步 ，为什么是n+1呢，因为只有这样同时移动的时候slow才能指向删除节点的上一个节点（方便做删除操作），如图：
• fast和slow同时移动，直到fast指向末尾，如题：

• 删除slow指向的下一个节点，如图：

  代码：

  class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode slow = dummy;
        ListNode fast = dummy;
        while (n-- > 0) {
            fast = fast.next;
        }
        // 记住 待删除节点slow 的上一节点
        ListNode prev = null;
        while (fast != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next;
        }
        // 上一节点的next指针绕过 待删除节点slow 直接指向slow的下一节点
        prev.next = slow.next;
        // 释放 待删除节点slow 的next指针, 这句删掉也能AC
        slow.next = null;
        return dummy.next;
    }
  }