刷题「链表」相关

找出两个链表的交点（简单）

该题要求时间复杂度为O(N)。如果想用两个指针分别指向两个链表，然后遍历求解，这样就需要两层循环，显然不符合时间复杂度O(N)的要求

对于正确解法的理解可以看下这张图⬇️

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        ha, hb = headA, headB
        while ha != hb:
            ha = ha.next if ha else headB
            hb = hb.next if hb else headA
        return ha

*另外补充下，如果只是判断两个链表是不是有共同结点，可以这么做

1. 将两个链表首尾相连，然后判断后一个链表是不是循环链表
2. 直接比较两个链表的尾结点相不相等

---

链表反转（简单）

这里要用到两个指针，一个指向当前结点，一个指向新链表的头结点（当前结点的上一个结点）

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        pre = None
        cur = head
        while cur:
            temp = cur.next 
            cur.next = pre
            pre = cur
            cur = temp
        return pre

*另外可以用递归的方式反转链表：

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if head is None or head.next is None:
            return head

        p = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return p

---

合并两个有序链表（简单）

下面是直接合并两个链表的操作，没有用到递归。

大体思路如下：

若两个链表都非空，则从最左边开始比较两个链表的结点值。谁小，要谁。并将小值对应的链表的指针后移一位。如此往复。直至其中一个链表的结点全部走完。最后，只需要将没走完的链表接在新链表的尾巴上就OK了。

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        head = ListNode(None)
        ret = head #ret用来记录新链表的头结点，并将其的next返回
        while l1 and l2:
            if l1.val > l2.val:
                head.next = ListNode(l2.val)
                head = head.next
                l2 = l2.next
            else:
                head.next = ListNode(l1.val)
                head = head.next
                l1 = l1.next

        if l1:
            head.next = l1
        if l2:
            head.next = l2
        return ret.next

下面是递归实现的代码：

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if not l1:
            return l2 #假设l1就是为空，所以只需返回l2就好了。
        if not l2:
            return l1
        if l1.val < l2.val: #假设l1只有一个结点，且比l2小。所以l1就是返回链表的头结点。
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2

递归的话，不要去纠结细节。要有宏观上的感觉。

递归我们只需要关注两件事 1.递归终止的条件是什么 2.递归体内部要做的是什么

比如这题，宏观上的递归思路就是：

递归终止的条件是什么？

终止条件就是，当其中之一的链表变为空时，则return。

递归体内部做的是是什么？

递归体内部做的是，比较两个链表当前结点值的大小。小的一方，则后边跟上递归调用。

递归调用传参该怎么传？

传参只需要将小的结点除去就OK了。用「.next」

我画了个图，便于理解。

---

删除链表的倒数第N个节点（中等）

直接写的思路是：

首先求出链表的长度。然后再从头遍历至待删除结点，将其删除即可。

这里有几个特殊情况需要注意：1）当length == n时，这时只需要将head.next返回就可以了。其中包括length == 1这种情况；2）当n == 1时，将最后一个结点置空即可。

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        if head is None:
            return None

        cur = head
        length = 0
        while cur:
            length += 1
            cur = cur.next

        if length == n:
            return head.next

        cur = head
        l = 1
        while l < length - n:
            l += 1
            cur = cur.next

        if n == 1:
            cur.next = None
        else:
            cur.next = cur.next.next
        return head

进阶版是用一趟扫描实现。

如果用一趟扫描，我们面对的问题是什么呢？我们不知道链表的长度，所以不知道该删除的结点到底在哪。

那么怎样才能找到那个待删除的结点呢？题目中给出了n的值，那可以从n的值作为突破点。

首先需要一个fast指针，让它先跑n步。因为fast = head，所以等fast跑完n步时，其实是指向第n+1个结点。此时，若fast指向空结点，那说明这满足length == n这种情况，所以要return head.next。

下面还需要一个slow结点，指向链表的头结点。因为这时fast已经跑出去n+1步了，所以只需让fast跑到链表的尾结点即可，这时slow指向的下一个结点就是待删除结点。

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        fast = head
        while n > 0:
            fast = fast.next
            n -= 1

        if fast is None:
            return head.next # length == n 的情况

        slow = head
        while fast.next is not None:
            fast = fast.next
            slow = slow.next

        slow.next = slow.next.next

        return head

---

两两交换链表中的节点（中等）

基本思路如下：

首先我们改造一下题目给的无头链表。将其变为带头结点的链表。这样可以让整体的操作更具一般性，不需要将前两个结点在循环外边交换。可以使每两个需要交换的结点的前面都有一个结点，这样可以让结点在交换时，链表不至于断掉，bbefore.next = after。看图理解下。

然后需要两个指针，分别指向待操作的两个结点的前一个结点，和后一个结点。交换结点的时候，处理好指针的指向就好。

#交换结点

before.next, after.next = after.next, before
bbefore.next = after

然后就循环就完了呗。若结点个数是偶数个，则都换。若奇数个，则最后一个不换。

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        new_head = ListNode(None)
        new_head.next = head
        bbefore = new_head
        while bbefore.next and bbefore.next.next:
            before, after = bbefore.next, bbefore.next.next

            before.next, after.next = after.next, before
            bbefore.next = after

            bbefore = before
            
        return new_head.next

---

删除排序链表中的重复元素（简单）

暴力解法，大体思路如下：

需要两个指针，一个指向当前结点，一个指向 需要判断后面是否有相同结点值 的结点。

然后就是遍历链表，判断tag.val == cur.val否？若相等，则删除。若不等，则说明这个有序链表中就不会再出现tag指向的结点值，所以tag后移一位。

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        tag = head
        cur = head
        while cur:
            if tag.val == cur.val:
                tag.next = cur.next
            else:
                tag = cur
            cur = cur.next

        return head

---

两数相加 II（中等）

考虑到链表中，位数的顺序和我们进行运算的顺序是相反的，那么我们可以使用「栈」这种「后进先出」的数据结构。

假设初始情况下，给的链表是如下图所示：

然后，我们将两个链表分别压进两个栈中。如下图所示：

压栈完成后，开始出栈，并进行运算。

每出栈一位就进行一步加法运算，这里要特别注意存在进位的情况。代码中我们用carry来表示进位值。

还有一个需要注意的地方是，我们在建立结果链表时，不是正序建立的，而是逆序建立的。这样加法运算完成后，直接可以返回正确的链表。当然如果不这么做的话，你也可以另外声明一个节点来记录正序链表的头指针，在加法运算完成后直接返回即可。

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        stack1, stack2 = [], []
        cur = l1
        while cur:
            stack1.append(cur.val)
            cur = cur.next
        cur = l2
        while cur:
            stack2.append(cur.val)
            cur = cur.next

        carry = 0
        ret = None
        while stack1 or stack2 or carry != 0:
            a = 0 if not stack1 else stack1.pop()
            b = 0 if not stack2 else stack2.pop()
            curnode = ListNode((a + b + carry) % 10)
            carry = (a + b + carry) // 10

            curnode.next = ret
            ret = curnode

        return ret

还有一种解法，是先将短的链表在高位补0，使两个链表长度相同。然后再反转两条链表。最后进行加法计算。如图所示。

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        a, b = l1, l2
        tag = 0 #短的（需要补0）的链表
        dif = 0 #两个链表的长度差
        #完成补0
        while a or b:
            tag = 1 if not a else 2
            if not a or not b:
                dif += 1
            if a: a = a.next
            if b: b = b.next

        if tag == 1:
            while dif > 0:
                t = ListNode(0)
                t.next = l1
                l1 = t
                dif -= 1
        elif tag == 2:
            while dif > 0:
                t = ListNode(0)
                t.next = l2
                l2 = t
                dif -= 1

        #反转两条链表
        pre = None
        while l1:
            t = l1.next
            l1.next = pre
            pre = l1
            l1 = t
        l1 = pre
        pre = None
        while l2:
            t = l2.next
            l2.next = pre
            pre = l2
            l2 = t
        l2 = pre

        #加法计算
        ret = None
        carry = 0
        while l1 or l2 or carry != 0:
            a = 0 if not l1 else l1.val
            b = 0 if not l2 else l2.val
            curnode = ListNode((a + b + carry) % 10)
            carry = (a + b + carry) // 10

            curnode.next = ret
            ret = curnode

            if l1: l1 = l1.next
            if l2: l2 = l2.next

        return ret

---

回文链表（简单）

思路：

首先新建一个链表，其内容为初始链表的反转。

然后同时遍历两条链表，并判断相应结点值是否相等，若有一个不等，则不是回文链表。否则，是。

先看是回文链表的图。可见对应结点的值都是相等的：

再看个不是回文链表的图：

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        cur = head
        new_head = None
        while cur:
            t = ListNode(cur.val)
            t.next = new_head
            new_head = t
            cur = cur.next

        while head:
            if head.val != new_head.val:
                return False
            head = head.next
            new_head = new_head.next

        return True

还有一种是利用list。大体思路和上面一样。

在pythonpython3中，借助切片可以很方便的生成列表的反向副本，生成反向列表副本的代码为：vals[::-1]。

点我了解更多关于切片的知识。

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        vals = []
        curnode = head
        while curnode is not None:
            vals.append(curnode.val)
            curnode = curnode.next
        return vals == vals[::-1]

这里提一个方法：可以设置快慢指针，慢指针一次走一步，快指针一次走两步。这样当快指针走到尾部时，慢指针正好走到中间。然后反转后半部分链表，将其和前半部分对比。完成后再将后半部分的链表复原（不复原也可，但是一般都不希望链表结构被改变）。

---

分隔链表（中等）

本题的难点我认为是，怎样计算划分后的每段链表的长度？请看下图：

class Solution:
    def splitListToParts(self, root: ListNode, k: int) -> List[ListNode]:
        # 现在我们假设链表长度为5，k=3

        # 返回值
        ret = []

        # 如果传来空链表，则直接返回长度为k的空list
        if not root:
            for i in range(k):
                ret.append(None)
            return ret

        # 计算链表的长度
        cur = root
        length = 0
        while cur:
            length += 1
            cur = cur.next

        # amount中每个值代表将链表分割后，每段的长度。具体的计算过程请看本题的第一张图。
        amount = []
        x = length // k
        y = length % k
        for i in range(k):
            t = x
            if y > 0:
                x += 1
                y -= 1
            amount.append(x)
            x = t
        # 现在amount的值为[2, 2, 1]

        amount.reverse()
        # 将amount反转一下，变为[1, 2, 2]。因为后面要用pop()方法来取其中的值。
        # 我们取值的顺序应该和最终生成的List的长度顺序保持一致。

        for times in range(k):
            temp_head = root

            pre = None
            l = amount.pop()
            for i in range(l):
                pre = root
                root = root.next
            if l != 0:
                pre.next = None
                ret.append(temp_head)
            else:
                ret.append(None)

        return ret

简化一下上个解法。

class Solution:
    def splitListToParts(self, root: ListNode, k: int) -> List[ListNode]:
        cur = root
        for N in range(1001):
            if not cur: break
            cur = cur.next
        width, remainder = divmod(N, k)

        ans = []
        cur = root
        for i in range(k):
            head = write = ListNode(None)
            tag = 1 if i < remainder else 0
            for j in range(width + tag):
                write.next = write = ListNode(cur.val)
                if cur: cur = cur.next
            ans.append(head.next)
        return ans

---

奇偶链表（中等）

思路如下：

需要两个指针，p用来指奇数位置，q用来指偶数位置。

每次循环都让p移到下一个奇数位置。q移到下一个偶数位置。这样就会产生两个子链表，一条为全部奇数的链表，另一条为全部偶数的链表。最后将两条链表首位连接即可。

对于链表总结点数为偶数个的情况，则需要一个pre_p指针来指向上一个p结点。方便最后连接奇、偶两个子链表。

看图。其中黄线代表最后连接奇、偶两个子链表。

class Solution:
    def oddEvenList(self, head: ListNode) -> ListNode:
        if not head: return None
        
        p = head
        q = head.next
        right = head.next
        pre_p = None
        while p and q:
            pre_p = p
            p.next = q.next
            p = q.next
            if p:
                q.next = p.next
                q = p.next
            else:
                q.next = None

        if not p:
            pre_p.next = right
        elif not p.next:
            p.next = right
            
        return head