Leetcode之链表题总结

Leetcode

概述

本文是个人对Leetcode上链表题目的总结。

题目类型

链表拼接

链表拼接，对于头结点不会变化的情况下，可以直接拼接，比如题目[旋转链表]。而对于头结点可能变化，则通常需要设置一个哑结点dummy，将需要的结点拼接到这个哑结点之后，最后返回dummy.next即可。

代码

    // 示例，两数相加
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        int incr = 0;
        while (l1 != null || l2 != null) {
            if (l1 != null) {
                incr += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                incr += l2.val;
                l2 = l2.next;
            }
            curr.next = new ListNode(incr % 10);
            curr = curr.next;
            incr /= 10;
        }
        if (incr > 0) {
            curr.next = new ListNode(incr);
        }
        return dummy.next;
    }

题目

链表反转

我们需要当前结点与前一个结点交换位置，因此，我们需要两个指针。

代码

    // 单链表反转
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
    // 双向链表反转
    public Node reverse(Node head) {
        Node prev = null;
        while (head != null) {
            Node next = head.next;
            head.next = prev;
            head.prev = next; // 相较于单向链表反转，增加前驱指针操作
            prev = head;
            head = next;
        }
        return prev;
    }

题目

获取倒数第K个结点

链表只能从头开始遍历，要获得倒数第K个结点，需要遍历n = size - k。使用双指针进行遍历，第一个指针先遍历

k个结点，那么之后该指针最多遍历n个结点。因此让第二个指针此时和它一起遍历到结束。

代码

    public int kthToLast(ListNode head, int k) {
        ListNode fast = head;
        for (int i = 0; i < k; i++) {
            fast = fast.next;
        }
        while (fast != null) {
            fast = fast.next;
            head = head.next;
        }
        return head.val;
    }

同理，如果想要获得链表中间结点，使用快慢指针即可：

    public ListNode middleNode(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

题目

链表是否有环

使用快慢指针，如果存在环，那么两个指针必定会相遇。

代码

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

题目

链表相交

使用双指针同时遍历，如果一个链表遍历完，则继续再另外一个链表遍历。如果相交，则两个指针会遇到相同结点。

代码

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode currA = headA, currB = headB;
        while (currA != null || currB != null) {
            if (currA == null) {
                currA = headB;
            }
            if (currB == null) {
                currB = headA;
            }
            if (currA == currB) {
                return currA;
            }
            currA = currA.next;
            currB = currB.next;
        }
        return null;
    }

题目