链表

链表基础

链表的特点？

答案：

• 非连续内存
• 插入删除O(1)
• 随机访问O(n)
• 动态大小

链表节点定义

public class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }
}

基本操作

反转链表（LeetCode 206）

答案：

// 迭代法
public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;

    while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

// 递归法
public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }

    ListNode newHead = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
}

合并两个有序链表（LeetCode 21）

答案：

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;

    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            curr.next = l1;
            l1 = l1.next;
        } else {
            curr.next = l2;
            l2 = l2.next;
        }
        curr = curr.next;
    }

    curr.next = l1 != null ? l1 : l2;
    return dummy.next;
}

删除链表的倒数第N个节点（LeetCode 19）

答案：

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;

    ListNode fast = dummy;
    ListNode slow = dummy;

    // fast先走n+1步
    for (int i = 0; i <= n; i++) {
        fast = fast.next;
    }

    // fast和slow一起走
    while (fast != null) {
        fast = fast.next;
        slow = slow.next;
    }

    // 删除节点
    slow.next = slow.next.next;
    return dummy.next;
}

快慢指针

环形链表（LeetCode 141）

答案：

public boolean hasCycle(ListNode head) {
    if (head == null) return false;

    ListNode slow = head;
    ListNode fast = head;

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

        if (slow == fast) {
            return true;
        }
    }
    return false;
}

环形链表II（LeetCode 142）

答案：

public ListNode detectCycle(ListNode head) {
    if (head == null) return null;

    ListNode slow = head;
    ListNode fast = head;

    // 判断是否有环
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;

        if (slow == fast) {
            // 找到环的入口
            ListNode ptr = head;
            while (ptr != slow) {
                ptr = ptr.next;
                slow = slow.next;
            }
            return ptr;
        }
    }
    return null;
}

链表的中间节点（LeetCode 876）

答案：

public ListNode middleNode(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;

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

复杂操作

两数相加（LeetCode 2）

答案：

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;
    int carry = 0;

    while (l1 != null || l2 != null || carry != 0) {
        int sum = carry;
        if (l1 != null) {
            sum += l1.val;
            l1 = l1.next;
        }
        if (l2 != null) {
            sum += l2.val;
            l2 = l2.next;
        }

        carry = sum / 10;
        curr.next = new ListNode(sum % 10);
        curr = curr.next;
    }
    return dummy.next;
}

排序链表（LeetCode 148）

答案：

public ListNode sortList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }

    // 找中点
    ListNode mid = getMid(head);
    ListNode left = sortList(head);
    ListNode right = sortList(mid);

    // 合并
    return merge(left, right);
}

private ListNode getMid(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    ListNode prev = null;

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

    if (prev != null) {
        prev.next = null;
    }
    return slow;
}

private ListNode merge(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;

    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            curr.next = l1;
            l1 = l1.next;
        } else {
            curr.next = l2;
            l2 = l2.next;
        }
        curr = curr.next;
    }

    curr.next = l1 != null ? l1 : l2;
    return dummy.next;
}

练习题

1. 回文链表（LeetCode 234）
2. 相交链表（LeetCode 160）
3. 旋转链表（LeetCode 61）
4. 重排链表（LeetCode 143）
5. 复制带随机指针的链表（LeetCode 138）