leetcode刷题之链表专题_leetcode链表专题

1.链表的操作

1.1 删除链表的倒数第N个节点

def removeNthFromEnd(self, head: ListNode, n: int) :
        a = head
        b = head
        
        for i in range(n):
            if a.next:
                a = a.next
            else:
                return head.next
                
        while a.next:
            a = a.next
            b = b.next
        b.next = b.next.next
        return head
1
2
3
4
5
6
7
8
9
10
11
12
13
14

1.2 合并两个有序链表

def mergeTwoLists(self, l1: ListNode, l2: ListNode):
        res=ListNode(None)
        node=res
        while l1 and l2:
            if l1.val<l2.val:
                node.next,l1=l1,l1.next
            else:
                node.next,l2=l2,l2.next
            node=node.next
        if l1:
            node.next=l1
        else:
            node.next=l2
        return res.next
1
2
3
4
5
6
7
8
9
10
11
12
13

1.3 合并K个排序链表

class Solution:
    def mergeKLists(self, lists: List[ListNode]):
        if not lists:return 
        n = len(lists)
        return self.merge(lists, 0, n-1)
    def merge(self,lists, left, right):
        if left == right:
            return lists[left]
        mid = left + (right - left) // 2
        l1 = self.merge(lists, left, mid)
        l2 = self.merge(lists, mid+1, right)
        return self.mergeTwoLists(l1, l2)
    def mergeTwoLists(self,l1, l2):
        if not l1:return l2
        if not l2:return l1
        if l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

1.4 两两交换链表中的节点

def swapPairs(self, head: ListNode):
        if not head or not head.next:
            return head
        l1=head
        l2=head.next
        l1.next=self.swapPairs(l2.next)
        l2.next=l1
        return l2
1
2
3
4
5
6
7

1.5 K个一组翻转链表

def reverseKGroup(self, head: ListNode, k: int):
        dummy = ListNode(0)
        p = dummy
        while True:
            count = k 
            stack = []
            tmp = head
            while count and tmp:
                stack.append(tmp)
                tmp = tmp.next
                count -= 1
            # 注意,目前tmp所在k+1位置
            # 说明剩下的链表不够k个,跳出循环
            if count : 
                p.next = head
                break
            # 翻转操作
            while stack:
                p.next = stack.pop()
                p = p.next
            #与剩下链表连接起来 
            p.next = tmp
            head = tmp
        
        return dummy.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

1.6 旋转链表

def rotateRight(self, head: ListNode, k: int) :
        if head is None or head.next is None: return head
        start, end, len = head
1
2