一周LeetCode习题精选——链表

LeetCode 206

本题是一道非常基础的反转单链表。首先想到的方法是把链表转换成数组直接逆序，这里不再细说。另外两种方法是递归和迭代。递归方法是指先反转最后两个节点，依次往前至全部反转。迭代法是从左至右反转。

class Solution:
    def reverseList(self, head): # 递归法
        if head is None or head.next is None:
            return head
        else:
            dummy = self.reverseList(head.next)
            head.next.next = head
            head.next = None
        return dummy

    def reverseList2(self, head): # 迭代法
        prev = None
        while head:
            # head.next, prev, head = prev, head, head.next 由于Python的特性，下面四行代码可写为一行
            curr = head
            head = head.next
            curr.next = prev
            prev = curr
        return prev

LeetCode 142

链接：Linked List Cycle II

本题判断一个链表是否有环，有环的话返回环的起始节点。本题使用快慢指针寻找环，也就是以前博文提到过的Floyd判圈算法。找到后怎样寻找起始节点呢？我们做一段证明。设链表头到环入口的距离为l1，入口到两指针相遇的距离为l2，c是环的长度，n为快指针在环中的遍历次数。当慢指针和快指针相遇时，慢指针走了l1 + l2的距离，快指针走了l1 + l2 + n * c的距离。而快指针走的步数是慢指针的两倍，所以可得2* (l1 + l2) = l1 + l2 + n * c ，整理后得l1 = (n - 1) * c + (c - l2)。令n等于1，可得l1 = c - l2。也就是说，链表头到环入口的距离和相遇距离到环入口的距离相等。在找到相遇节点后，头节点和慢/快指针同步走下去，相遇时即为环入口。

class Solution(object):
    def detectCycle(self, head):
        slow = fast = head
        while fast and fast.next:
            slow, fast = slow.next, fast.next.next
            if slow == fast:
                break
        else:
            return None

        while head != slow:
            head, slow = head.next, slow.next
        return head

LeetCode 148

链接：Sort List

本题为链表排序，使用归并排序解决，基本思路是：找到链表的中间节点，然后递归对前半部分和后半部分分别进行归并排序，最后合并两个有序链表。找中间节点需要使用快慢指针。快指针走的步数是慢指针的两倍，当快指针走到链表结尾时，慢指针正好走到中央。合并链表部分记录了迭代法和递归法两种链表合并方法。

class Solution(object):
    def sortList(self, head):
        if not head or not head.next:
            return head

        pre = None
        slow = fast = head
        while fast and fast.next:
            pre, slow, fast = slow, slow.next, fast.next.next
        pre.next = None # 截断链表左半部分

        return self.merge(self.sortList(head), self.sortList(slow))

    def merge(self, h1, h2): # 迭代法
        dummy = tail = ListNode(None)
        while h1 and h2:
            if h1.val < h2.val:
                tail.next, h1 = h1, h1.next
            else:
                tail.next, h2 = h2, h2.next
            tail = tail.next

        tail.next = h1 or h2
        return dummy.next

    def merge2(self, l1, l2): # 递归法
        if not l1 or not l2:
            return l1 or l2
        if l1.val < l2.val:
            l1.next = self.merge2(l1.next, l2)
            return l1
        else:
            l2.next = self.merge2(l1, l2.next)
            return l2

参考资料：经典算法——单链表反转的递归方法和非递归方法 leetcode题解 problem 142 Linked List Cycle II

LeetCode 206#

LeetCode 142#

LeetCode 148#

LeetCode 206

LeetCode 142

LeetCode 148