链表

160. 相交链表

java

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode A = headA;
        ListNode B = headB;
        while (A != B) {
            A = A == null ? headB : A.next;
            B = B == null ? headA : B.next;
        }
        return A;
    }
}

206. 反转链表

java

// 使用虚拟头节点进行头插入，官解不需要头节点也可以
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode dummy = new ListNode();

        ListNode cur = head, temp;
        while (cur != null) {
            temp = cur.next;
            cur.next = dummy.next;
            dummy.next = cur;
            cur = temp;
        }
        return dummy.next;
    }
}

234. 回文链表

java

class Solution {
    public boolean isPalindrome(ListNode head) {
        // 方法一：数组存储后判断
        // 方法二：快慢指针，慢指针走到中间一段并且翻转前半段链表
        // ----><----变为<----<----奇数需要处理slow，newhead和slow分别指向两段起点
        ListNode slow = head, fast = head, temp = null, newhead = null;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            temp = slow.next;
            slow.next = newhead;
            newhead = slow;
            slow = temp;
        }
        // 1 2 3 3 2 1 slow和fast刚好循环3次
        // 1 2 3 2 1 slow和fast循环2次
        if (fast != null) {
            slow = slow.next;
        }
        while (slow != null) {
            if (newhead.val != slow.val) {
                return false;
            }
            slow = slow.next;
            newhead = newhead.next;
        }
        return true;
    }
}

141. 环形链表

java

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }
}

142. 环形链表 II

java

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

21. 合并两个有序链表

java

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode();
        ListNode tail = dummy;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                tail.next = list1;
                list1 = list1.next;
            } else {
                tail.next = list2;
                list2 = list2.next;
            }
            tail = tail.next;
        }

        // 下面可以三目运算符
        if (list1 != null) {
            tail.next = list1;
        } else {
            tail.next = list2;
        }
        return dummy.next;
    }
}

2. 两数相加

java

// 进位carrybit，优先看灵神的吧
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int carrybit = 0;
        ListNode dummy = new ListNode();
        ListNode tail = dummy;
        while (l1 != null && l2 != null) {
            int sum = l1.val + l2.val + carrybit;
            carrybit = sum / 10;
            tail.next = new ListNode(sum % 10);
            tail = tail.next;
            l1 = l1.next;
            l2 = l2.next;
        }
        tail.next = l1 != null ? l1 : l2;
        while (tail.next != null && carrybit != 0) {
            int sum = tail.next.val + carrybit;
            carrybit = sum / 10;
            tail.next.val = (sum % 10);
            tail = tail.next;
        }
        if (carrybit != 0) {
            tail.next = new ListNode(1);
        }

        return dummy.next;
    }
}


// 灵神代码更优雅
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(); // 哨兵节点
        ListNode cur = dummy;
        int carry = 0; // 进位
        while (l1 != null || l2 != null || carry != 0) { // 有一个不是空节点，或者还有进位，就继续迭代
            if (l1 != null) carry += l1.val; // 节点值和进位加在一起
            if (l2 != null) carry += l2.val; // 节点值和进位加在一起
            cur = cur.next = new ListNode(carry % 10); // 每个节点保存一个数位
            carry /= 10; // 新的进位
            if (l1 != null) l1 = l1.next; // 下一个节点
            if (l2 != null) l2 = l2.next; // 下一个节点
        }
        return dummy.next; // 哨兵节点的下一个节点就是头节点
    }
}

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

java

// 解法一：双指针，头节点，pre指向当前节点cur前一个，cur先走n步4，然后一起走
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode pre = dummy, cur = head;
        while (n-- != 0) {
            cur = cur.next;
        }
        while (cur != null) {
            cur = cur.next;
            pre = pre.next;
        }
        pre.next = pre.next.next;
        return dummy.next;
    }
    
// 解法二：递归，需要返回值和一个共享的倒数idx记录
class Solution {
    private int idx; // 此处的idx需要在每层递归可见，不能--n

    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) {
            return null;
        }
        head.next = removeNthFromEnd(head.next, n);
        if (++idx == n) {
            return head.next;
        }
        return head;
    }
}

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

java

// 哨兵节点，然后三个指针 pre node1 node2
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        ListNode pre = dummy, node1, node2;

        while (pre.next != null && pre.next.next != null) {
            node1 = pre.next;
            node2 = node1.next;

            node1.next = node2.next;
            node2.next = node1;
            pre.next = node2;
            pre = pre.next.next;
        }
        return dummy.next;
    }
}

148. 排序链表

java

// 本题目细节：
// 1. 归并排序，单个节点以内无需排序直接返回
// 2. 多个节点，中间插入null拆分两段，注意fast预先走一步再进入循环（原因可以考虑2个节点情况）
// 3. 排序后的返回头需要再次利用，不能用前面的了
class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode slow = head, fast = head.next; // fast先走一步方便利用slow断开原有链表，后面fast就没用了
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode temp = slow.next;
        slow.next = null;
        ListNode left = sortList(head);
        ListNode right = sortList(temp);
        // 上面已经拆分为两端并递归，开始合并，这里就是两个普通的链表进行合并操作，借助头节点
        ListNode dummy = new ListNode();
        ListNode tail = dummy;
        while (left != null && right != null) {
            if (left.val < right.val) {
                tail.next = left;
                left = left.next;
            } else {
                tail.next = right;
                right = right.next;
            }
            tail = tail.next;
        }
        tail.next = left != null ? left : right;
        return dummy.next;
    }
}

链表 ​

链表