Leetcode刷题笔记之专题（1）链表求解 Python实现

概述第一专题：链表求解1.leetcode224反转链表(easy)思路一：迭代迭代需要三个指针，pre，cur，nxt，分别按顺序指向三个节点三个指针的初始化：pre指向空节点，cur指向头结点head，nxt指向head.next因为head.next可能不存在，nxt在循环中定义，这样如果head为空就不会进入循环迭代过程nxt 第一专题： 链表求解1. leetcode 224 反转链表(easy)思路一： 迭代

迭代需要三个指针，pre，cur，nxt，分别按顺序指向三个节点
三个指针的初始化：pre指向空节点，cur指向头结点head，nxt指向head.next
因为head.next可能不存在，nxt在循环中定义，这样如果head为空就不会进入循环
迭代过程

nxt指向cur.nextcur.next指向prepre移动到cur位置cur移动到nxt位置

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

使用python多元赋值的特性求解：

先模拟出这个过程：使用1->2->3->4->5模拟作为例子

先初始化出：curr表示当前指针指向的对象为head；res代表结果指针,初始化为None。while循环进行res,curr赋值情况如下表：

class Solution:    def reverseList(self, head: ListNode) -> ListNode:        curr,res = head,None        while curr:            res,res.next,curr = curr,res,curr.next        return res

次数	res = curr: res	res.next=res : res	curr = curr.next: curr
1	1->2->3->4->5	1->None	2->3->4->5
2	2->3->4->5	2->1->None	3->4->5
3	3->4->5	3->2->1->None	4->5
4	4->5	4->3->2->1->None	5
5	5	5->4->3->2->1->None	None

2. leetcode 21合并两个有序链表（easy)一. 递归法：

# DeFinition for singly-linked List.# class ListNode:#     def __init__(self, val=0, next=None):#         self.val = val#         self.next = nextclass Solution:    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:        if l1 is None: return l2        if l2 is None: 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

二. 迭代法

解决有序链表的一般解决思路，使用python的特性，先定义一个哨兵结点res，然后在遍历过程中维护一个pre指针，在循环迭代的过程中找到每一次的需求。

class Solution:    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:        if l1 is None: return l2        if l2 is None: return l1        res = ListNode(0) # 首先预定义一个栈        pre = ListNode(0)        while l1 and l2:            if l1.val > l2.val:                pre.next = l2                l2 = l2.next            else:                pre.next = l1                l1 = l1.next            pre = pre.next        pre.next = l1 if l1 else l2        return res.next           

3. leetcode234 回文链表(easy)一. 数组法

将链表的值复制到数组中后使用双指针法进行求解

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

时间复杂度O（n)，空间复杂度O（n), 其中链表转化为数组的时间复杂度为O(n)，空间复杂度也为O(n)。双指针数组对比时间复杂度为O(n)，空间复杂度也为O(n)。因此总的来看时间复杂度为O(n)，算法复杂度为O（n)。

二. 快慢指针法

。。。

@L_404_13@4. leetcode26 删除有序数组中的重复项（easy)

使用双指针的方法：快指针用来判断前后是否相等，慢指针用来将不相等的值按顺序存储。

class Solution:    def removeDuplicates(self, nums: List[int]) -> int:        # 使用双指针的方法进行求解        if not nums: return 0        j = 0        for i in range(1,len(nums)):            if nums[i-1] != nums[i]:                j +=1                nums[j] = nums[i]        return j+1

5. leetcode83. 删除排序链表中的重复元素

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

6. leetcode61. 旋转链表遍历出链表的长度计算出链表需要从链表的哪个位置截断将前半部分接到后半部分的尾部，然后进行输出

# DeFinition for singly-linked List.# class ListNode:#     def __init__(self, val=0, next=None):#         self.val = val#         self.next = nextclass Solution:    def rotateRight(self, head: ListNode, k: int) -> ListNode:        if not head or not head.next: return head        curr = head        n = 0        while curr:            n+=1            curr = curr.next        k = k % n        if k == 0: return head        p = head        for i in range(n-k-1):            p = p.next        nxt = p.next        p.next = None        new_nxt = nxt

7. leetcode1669. 合并两个链表

# DeFinition for singly-linked List.# class ListNode:#     def __init__(self, val=0, next=None):#         self.val = val#         self.next = nextclass Solution:    def mergeInBetween(self, List1: ListNode, a: int, b: int, List2: ListNode) -> ListNode:        curr = List1        for i in range(b+1):            if i < a-1: curr = curr.next            elif i == a-1:                nxt = curr.next                curr.next = List2            else: nxt = nxt.next        while curr.next:            curr = curr.next        curr.next = nxt        return List1

8. leetcode23. 合并K个升序链表（hard)

假设链表的总长度为n，我们可以先得出k个升序链表的总长度，然后使用一个列表Docker存储当前K个链表的当前头节点的值，如果当前的链表为空，那么令其值为10**5（该值大于题目所规定的链表的最大值）。然后循环查找Docker中的最小值，并将其链接结果链表中。时间复杂度：O(KN), 空间复杂度O（K）

# DeFinition for singly-linked List.# class ListNode:#     def __init__(self, val=0, next=None):#         self.val = val#         self.next = nextclass Solution:    def mergeKLists(self, Lists: List[ListNode]) -> ListNode:        res = ListNode(0)        curr = res        count = 0            # 查看所有链表的总长度count        for item in Lists:            while item:                count+= 1                item = item.next        if count == 0: return None        docker = []        for lst in Lists:                if lst is not None:                    docker.append(lst.val)                else:                    docker.append(10**5) # 10**5代表无法取到的最大值        while count > 0:     # 遍历count次将链表组合到res链表中            count -= 1            curr_min = min(docker)            for i in range(len(docker)):                if docker[i] == curr_min:                    tmp = docker[i]                    curr.next = Lists[i]                    curr = curr.next                    if Lists[i].next:                        docker[i] = Lists[i].next.val                        Lists[i] = Lists[i].next                    else:                        docker[i] = 10**5                    break        return res.next

总结

以上是内存溢出为你收集整理的Leetcode刷题笔记之专题（1）链表求解 Python实现全部内容，希望文章能够帮你解决Leetcode刷题笔记之专题（1）链表求解 Python实现所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。