链表专题

链表题最好画图来说明整个流程。

LeetCode

2. 两数相加

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。
例如 2 -> 4 -> 3 表示 342
需要注意进位的问题，还有头结点的使用。

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(-1), nextNode = dummy;
    int carry = 0;
    while (l1 != null || l2 != null || carry != 0) {
        int v1 = (l1 != null ? l1.val : 0);
        int v2 = (l2 != null ? l2.val : 0);
        ListNode newNode = new ListNode((v1 + v2 + carry)%10);
        carry = (v1 + v2 + carry) / 10;
        nextNode.next = newNode;
        nextNode = newNode;
        l1 = (l1 != null ? l1.next : null);
        l2 = (l2 != null ? l2.next : null);
    }
    return dummy.next;
}

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

快慢指针实现一遍扫描

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    ListNode first = dummy, second = dummy;
    while (n-- > 0) {
        first = first.next;
        if (first == null)  break;
    }
    if (n > 0)  return head;
    while (first.next != null) {
        first = first.next;
        second = second.next;
    }
    ListNode removeNode = second.next;
    second.next = second.next.next;
    removeNode.next = null;
    return dummy.next;
}

24. 两两交换链表中的节点

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

public ListNode swapPairs(ListNode head) {
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    ListNode prev1 = dummy, prev2 = dummy.next;
    while (prev1.next != null && prev2.next != null) {
        ListNode temp = prev2.next.next;
        prev1.next = prev2.next;
        prev1.next.next = prev2;
        prev2.next = temp;
        prev1 = prev2;    prev2 = temp;
    }
    return dummy.next;
}

142. 环形链表 II

返回链表入环的第一个节点，如果不存在环，则返回null。

public ListNode detectCycle(ListNode head) {
    if (head == null || head.next == null)  return null;
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (fast == slow)   break;
    }
    if (fast == null || fast.next == null)  return null;
    //找环
    slow = head;
    while (slow != fast) {
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
}

快慢指针第一次相遇的点将环分为两部分，一部分是l，另一部分是l，因此有第一个等式的成立，其中k表示快指针走的圈数，然后等式可以化为第二个。
第二个等式的含义是，一个指针走过l的距离等同于另一个指针走了k圈，再减去l的距离。通常小环的话有k>1，大环的话k=1。（大环比较好理解，直接有l等于l）

143. 重排链表

给定一个单链表 L：L→L→…→L__n→L将其重新排列后变为： L→L__n→L→L__n→L→L__n→…

//找中间节点，然后逆转中间节点以后的
public void reorderList(ListNode head) {
    if (head == null)   return ;
    ListNode middle = findMiddleNode(head);
    ListNode second = reverseList(middle.next);
    middle.next = null;
    ListNode dummy = new ListNode(-1, head), curNode = dummy;
    ListNode curNode1 = head, curNode2 = second;
    while (curNode1 != null && curNode2 != null) {
        curNode.next = curNode1;
        curNode1 = curNode1.next;
        curNode = curNode.next;
        curNode.next = curNode2;
        curNode = curNode.next;
        curNode2 = curNode2.next;
    }
    curNode.next = curNode1;        //奇数个节点的情况
    dummy.next = null;
}
private ListNode findMiddleNode(ListNode head) {
    ListNode fast = head, slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    return slow;
}
private ListNode reverseList(ListNode head) {
    if (head == null)   return null;
    ListNode curNode = head, reversed = null;
    while (curNode != null) {
        ListNode temp = curNode.next;
        curNode.next = reversed;
        reversed = curNode;
        curNode = temp;
    }
    return reversed;
}

要一点技巧，找到中间节点，然后将逆转中间节点之后的链表，这样就相当于两个链表的合并了。

234. 回文链表

判断链表是否回文。要求时间复杂度为O(n)，空间复杂度为O(1)。
由于链表的顺序读取性质，如果想要判断回文而且要满足时间复杂度的话，意味着要改变链表的结构，自然想到反转链表。因此思路是，先找到中间节点，然后反转链表后半部分成为一个新链表，判断链表两部分是否相同，最后不要忘记恢复链表。此外，自然要想到奇数个节点的情况，多余的那个节点是放在哪部分链表中才不会需要特判，即中间节点选择哪一个，这里就直接放在了前半部分链表中（第6行代码），由于没有改变middleNode的指向，所以恢复链表直接反转就行了。
官方递归解法还挺有趣的，可以看一下。

public boolean isPalindrome(ListNode head) {
    if (head == null)   return true;
    //获得链表长度
    int nums = calculateListNums(head);
    ListNode curNode1 = head, middleNode = head;
    for (int i = 1; i < (nums + 1)/2; i++) {
        middleNode = middleNode.next;
    }
    ListNode head2 = reverseList(middleNode.next), curNode2 = head2;
    while (curNode1 != null && curNode2 != null) {
        if (curNode1.val != curNode2.val) {
            reverseList(head2);                //不要忘记恢复链表
            return false;
        }
        curNode1 = curNode1.next;
        curNode2 = curNode2.next;
    }
    reverseList(head2);                        //不要忘记恢复链表
    return true;
}