24.两两交换链表中的节点 (opens new window)

这道题，要求是两两交换。并且不能是改变值，而是真的要发生位置交换。

解法一：递归

思路：首先，如果head == null或者 head.next ==null的 时候，就返回head。因为不满足两个节点都存在了

图1：头节点是1

图2：将第二个标记为头节点

图3：将1的next 设置为swapPairs((2).next), 后面的调换我们先不管，假设后面调换完了。

图4：将新的头节点的next设置为1

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {

        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = head.next;
        head.next = swapPairs(newHead.next);
        newHead.next = head;
        return newHead;
    }

}

解法2：虚拟头节点

具体思路如下图：

定一个虚拟头节点，然后新建几个变量，用来存储头节点后面的第1、2、3个节点。

按照顺序设置每个节点的next。

设置完之后，将当前的临时头节点设置为头节点的第三个。这样的话，前面调换的两个就不会再变动了

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
                ListNode virtualHead = new ListNode(0);
        virtualHead.next = head;

        ListNode cur = virtualHead;

        //这里是将cur后面的第一二个节点两两调换
        while (cur.next != null && cur.next.next != null) { 
            ListNode temp = cur.next.next.next;
            ListNode firstNode = cur.next;
            ListNode secondNode = cur.next.next;
            
            cur.next = secondNode;
            secondNode.next = firstNode;
            firstNode.next = temp;
            cur = firstNode;
        }
        return virtualHead.next;

    }
}

19.删除链表的倒数第N个结点 (opens new window)

虚拟头节点和双指针的结合。

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode vNode = new ListNode(-1);
        vNode.next = head;
        ListNode slow = vNode;
        ListNode fast = vNode;

        for(int i=0;i<n;i++){
            fast = fast.next;
        }

        while(fast.next!=null){
            fast = fast.next;
            slow = slow.next;
        }

        slow.next = slow.next.next;

        return vNode.next;
    }
}

面试题02.07.链表相交 (opens new window)

AB链表长度可能不同，先扫描一遍AB长度有多少。长的先走几步，对齐。然后AB一起走。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null){
            return null;
        }

        int aLenght = 1;
        int bLenght = 1;

        ListNode a = headA;
        ListNode b = headB;
        while(a.next!=null){
            aLenght++;
            a = a.next;
        }
        while(b.next!=null){
            bLenght++;
            b = b.next;
        }

        if(aLenght>bLenght){
            int n = aLenght-bLenght;
            //a先走N步
            for(int i = 0;i<n;i++){
                headA = headA.next;
            }
        }else if (aLenght<bLenght){
            int n = bLenght-aLenght;
            //b先走N步
            for(int i = 0;i<n;i++){
                headB = headB.next;
            }
        }

      while(headB!=null){
                if(headB.equals(headA)){
                    return headB;
                }
                headA = headA.next;
                headB = headB.next;
            }

        return null;
    }
}

142.环形链表Ⅱ (opens new window)

这个题目有点难度。如果用hashSet做的话，很简单。但是增加了空间复杂度

public class Solution {
    public ListNode detectCycle(ListNode head) {
        HashSet<ListNode> set = new HashSet<>();
        while(head!=null && head.next!=null){
            if(!set.contains(head)){
                set.add(head);
                head = head.next;
            }else{
                return head;
            }
        }
        return null;
    }
}

所以，我们采用快慢指针的做法。

假设环的形状是这个样子

定义一个快指针，每次走两步。慢指针一次走一步。那么它们同时出发，如果有环的话，他们一定是在慢指针进入环的第一圈的时候相遇了。

相遇的时候，我们指导慢指针走的路程是x+y，快指针速度是慢指针的两倍，所以快指针走了2(x+y)

但是由图可以看出来，实际上，快指针走的路程也可以用x+y+n(y+z)表示。

n的意思是快指针已经在环里面饶了N圈才遇到的慢指针

所以有等式 2(x+y) = x+y+ n(y+z)

稍加移项就可以得到 x = n(y+z) -y

在一个长度为(y+z)的环里面，向后走y步其实就是向前走z步。

并且 x = n(y+z) -y 可以变为 x = (n-1)(y+z) +z

我们不需要求出N。

只需要在相遇的时候，在相遇点和头结点一起以相同的速度出发，就可以知道他们还是会在入口相遇的。

这么说的有点抽象，归纳总结不够好。还是看视频吧。

下面是代码

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast!=null&& fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
            if(slow.equals(fast)){
                ListNode index1 = head;
                ListNode index2 = slow;
                while(!index1.equals(index2)){
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
            }
        }
        return null;
    }
}