Linked List in Python

原题

5月16日

这两天写了两道 LeetCode 题目，都是关于单向链表(Singly linked list)的，分别是 2. Add Two Numbers (Medium) 以及 21. Merge Two Sorted Lists (Easy)。由简到难，先做了后者再去尝试了前者。

非常巧的是，在做第21题前，刚好了解到了归并排序(Merge sort)，并且试着用python写了一个归并脚本，只不过当时只用了 python 内置的数组。

5月27日更新

刚刚完成了 148. Sort List (Medium)，用单向链表实现排序。

单向链表与节点

单向链表，顾名思义只有从前往后的单向连接，反之则不行。使用单向列表的好处在于，当需要在链表中插入数据时，只需要遍历链表找到需要插入数据的位置，将前一个节点改为指向新节点，并且让新节点指向后继节点即可，省去了数组中元素后移的麻烦。删除同理。

在实际代码中往往用第一个节点来指代整个链表。

在 LeetCode 题目中，单个节点的定义如下：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

也就是说，一个节点只有它本身的值(val)以及next两个属性，其中 next 用来指向下一个节点。通过 list1 = list.next 来移动到下一个节点，当 list1 == None 时（或 list1.next == None，即没有后继节点），链表结束。

一般情况下还会定义一个 LinkedList 类，把查找、插入、删除等函数都打包进类里。LeetCode这里属于是极简配置了，但不影响数据结构的讨论。

解题

先看简单的第21题。

第21题 合并有序链表

21. Merge Two Sorted Lists

题目要求将两个由小到大排序的单向链表合并成一个，输入和输出都是 ListNode 实例。

先上代码：

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:   
        
        # 如果有空链表，直接返回另一个链表
        if not list1:
            return list2 
        elif not list2:
            return list1
        
        # 将第一个值小的初始化为输出链表的第一个值
        if list1.val <= list2.val:
            output = list1
            list1 = list1.next
        else:
            output = list2
            list2 = list2.next
        head = output

        while list1 != None and list2 != None:
            # 将较小的值赋给current，并将链表移到下一个节点
            if list1.val <= list2.val:
                current = list1
                list1 = list1.next
            else:
                current = list2
                list2 = list2.next
            output.next = current
            output = output.next

        # 如果有一个链表已经没有后继节点
        # 则直接将另一个链表剩余节点加在输出链表末尾
        if list1 != None:
            while list1 != None:
                output.next = list1
                list1 = list1.next
                output = output.next
        elif list2 != None:
            while list2 != None:
                output.next = list2
                list2 = list2.next
                output = output.next

        return head #用链表第一个节点来指代链表，只要返回第一个节点即可

这里值得注意的是和python内置的数组一样，while list1 != None: 和 while list1: 意义相同，都表示‘不为空时’。当节点为 None 时，逻辑值相当于 False。

这个解法看起来略显繁琐，但是运行时间和占用内存都并不大，也很容易理解。

第2题 反向求和

2. Add Two Numbers (Medium)

这道题目本身还挺搞的，把两个需要相加的数倒了过来，每个数位都放在链表的节点中，如下所示：

这里注意到的是数字高位和低位颠倒了过来，因此相加时新的数位产生在最右侧。

代码如下：

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        output = ListNode()
        header = output
        upper = 0 # 表示进位
        while l1 != None:
            if l2 != None:
                ans = l1.val + l2.val + upper
                upper = 0
                if ans > 9:
                    output.val = ans - 10
                    upper = 1
                else:
                    output.val = ans
                l2 = l2.next
            else:
                ans = l1.val + upper
                upper = 0
                if ans > 9:
                    output.val = ans - 10
                    upper = 1
                else:
                    output.val = ans
            
            # 当达到链表末尾时，需要考虑是否要留出一位来存放进位
            # 第40行同理
            if l1.next != None or upper == 1 or l2 != None:
                output.next = ListNode()
            output = output.next
            l1 = l1.next
            
        while l2 != None:
            ans = l2.val + upper
            upper = 0
            if ans > 9:
                output.val = ans - 10
                upper = 1
            else: 
                output.val = ans
            if l2.next != None or upper == 1:
                output.next = ListNode()
            output = output.next
            l2 = l2.next
            
        if upper == 1:
            output.val = 1
        
        return header

思路和上一题一样，取出一个数后移动节点，需要注意的是逢十进一。此处还有优化空间。

但是这次不同的是我选择新创建了一个节点实例来表示输出链表(output = ListNode())，实际上和使用已有链表来初始化作用相同。

第148题 链表排序

148. Sort List (Medium)

题目要求很简单，将输入链表排序后输出。

冒泡

很显然，最容易想到和代码实现的排序方法就是冒泡排序。以下是我第一次尝试时写的代码。

class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # bubble sort
        current = head
        exchange = True
        while exchange:
            exchange = False
            while current and current.next:
                if current.val > current.next.val:
                    mid = current.val
                    current.val = current.next.val
                    current.next.val = mid
                    exchange = True
                current = current.next
            current = head
        return head

但非常可惜的是，当测试用例极大时，使用冒泡排序会超时。

Time Limit Exceeded

归并

意外发现用单向链表实现归并排序会比用 list 方便很多，尤其是归并这一步，但是不太容易想到。

class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # merge sort
        if head is None or head.next is None:
            return head
        left = head
        right = self.get_mid(head)
        transection = right.next
        right.next = None
        left = self.sortList(left)
        right = self.sortList(transection)
        merge = self.merge(left, right)
        return merge
        
    def merge(self, LN1, LN2):
        tail = ListNode()
        out = tail
        while LN1 and LN2:
            if LN1.val < LN2.val:
                tail.next = LN1
                LN1 = LN1.next
            else:
                tail.next = LN2
                LN2 = LN2.next
            tail = tail.next
        if LN1:
            tail.next = LN1
        elif LN2:
            tail.next = LN2
        out = out.next
        return out
            
    def get_mid(self, head):
        a = head
        b = head.next
        while True:
            if b and b.next:
                a = a.next
                b = b.next.next
            else:
                return a

笔记

在整个编程过程中，最需要注意的还是链表的末尾。一不小心经常容易出现赋值给 None 或者取值 None.next 的报错。