leetcode刷题之链表必刷题（python实现）

深藏阁楼爱情的钟 2023-01-13 09:40 136阅读 0赞

最近重新回顾了一下链表，在自己手动写了链表的生成以及相应的增删查改操作后，对链表的理解更加深刻，于是在leetcode上刷了对应的习题。

王争老师列举了一些链表必刷题，感觉有必要做一下这些习题。

链表的必刷题有：

*  单链表反转
 *  链表中环的检测
 *  两个有序的链表合并
 *  删除链表倒数第n个结点
 *  求链表的中间结点

### 文章目录 ###

*   *   *   *  206. \[反转链表\](https://leetcode-cn.com/problems/reverse-linked-list/)
             *   *  递归实现：
                 *  迭代实现
             *  92. \[反转链表 II\](https://leetcode-cn.com/problems/reverse-linked-list-ii/)
             *  剑指 Offer 22. \[链表中倒数第k个节点\](https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/)
             *   *  使用快慢指针
                 *  先遍历再取节点
             *  19. \[删除链表的倒数第 N 个结点\](https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/)
             *  876. \[链表的中间结点\](https://leetcode-cn.com/problems/middle-of-the-linked-list/)
             *   *  快慢指针法
                 *  先遍历再求节点
             *  21. \[合并两个有序链表\](https://leetcode-cn.com/problems/merge-two-sorted-lists/)
             *  141. \[环形链表\](https://leetcode-cn.com/problems/linked-list-cycle/)
             *  142. \[环形链表 II\](https://leetcode-cn.com/problems/linked-list-cycle-ii/)

#### 206. [反转链表][Link 1] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2F5YW5nYW5uOTE1_size_16_color_FFFFFF_t_70]

这道题可以用迭代或者递归实现。

递归和迭代的思路都是不断反转两个节点。

##### 递归实现： #####

# Definition for singly-linked list.
    # class ListNode(object):
    # def __init__(self, val=0, next=None):
    # self.val = val
    # self.next = next
    class Solution(object):
        def reverseList(self, head):
            """ :type head: ListNode :rtype: ListNode """
            # 有一个节点或者没有节点时，直接返回列表
            if not head or not head.next:
                return head
    
            pre, node = head, head.next
            while node:
                pre, node = self.__reverse_two(pre, node)
            
            head.next = None
            head = pre
            return head
    
        def __reverse_two(self, pre, node):
            # 反转两个节点
            tmp = node.next
            node.next = pre
            pre, node = node, tmp
            return pre, node

##### 迭代实现 #####

# Definition for singly-linked list.
    # class ListNode(object):
    # def __init__(self, val=0, next=None):
    # self.val = val
    # self.next = next
    class Solution(object):
        def reverseList(self, head):
            """ :type head: ListNode :rtype: ListNode """
            if not head or not head.next:
                return head
            pre, node = head, head.next
            while node:
                temp = node.next
                node.next = pre
                pre = node
                node = temp
            
            head.next = None
            return pre

#### 92. [反转链表 II][II] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2F5YW5nYW5uOTE1_size_16_color_FFFFFF_t_70 1]

反转链表92的题目可以在反转链表206的题目上修改。

反转的逻辑可以复用。

这里主要是要找到反转的起始节点和终止节点，同时要保存剩下的节点。

# Definition for singly-linked list.
    # class ListNode(object):
    # def __init__(self, val=0, next=None):
    # self.val = val
    # self.next = next
    class Solution(object):
        def reverseBetween(self, head, left, right):
            """ :type head: ListNode :type left: int :type right: int :rtype: ListNode """
            if not head.next:
                return head
            
            fake_head = ListNode(-1)
            fake_head.next = head
            pre = fake_head
            # 得到反转起始节点的前向节点
            for i in range(left - 1):
                pre = pre.next
    
            reverse_end = pre
            # 得到反转终止节点
            for i in range(right - left + 1):
                reverse_end = reverse_end.next
            
            # 剩余不反转的节点
            end_node = reverse_end.next
            # 反转起始节点
            reverse_start = pre.next
            # 反转终止节点指向None， 反转起始节点的前向节点指向None
            reverse_end.next = None
            pre.next = None
    
            # 反转中间部分的节点
            # 反转起始节点reverse_start, 终止是 reverse_end
            pre_, node_ = reverse_start, reverse_start.next
            while node_:
                pre_, node_ = self.__reverse(pre_, node_)
            
            pre.next = pre_
            reverse_start.next = end_node
            return fake_head.next
    
        # 利用递归反转，也可以使用迭代
        def __reverse(self, pre, node):
            tmp = node.next
            node.next = pre
            pre, node = node, tmp
            return pre, node

#### 剑指 Offer 22. [链表中倒数第k个节点][k] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2F5YW5nYW5uOTE1_size_16_color_FFFFFF_t_70 2]

求倒数第k个节点有两种方法，第一种是使用快慢指针，第二种就是先求出链表的长度，再遍历得到对应节点

##### 使用快慢指针 #####

使用快慢指针可以只扫描一次。

# class ListNode(object):
    # def __init__(self, x):
    # self.val = x
    # self.next = None
    
    class Solution(object):
        def getKthFromEnd(self, head, k):
            """ :type head: ListNode :type k: int :rtype: ListNode """
            if not head or not head.next:
                return head
            
            fast = slow = head
            # 快指针先走k步
            for i in range(k):
                fast = fast.next
            while fast:
                slow = slow.next
                fast = fast.next
            # 当快指针走完的时候，慢指针就位于该节点
            return slow

##### 先遍历再取节点 #####

# class ListNode(object):
    # def __init__(self, x):
    # self.val = x
    # self.next = None
    
    class Solution(object):
        def getKthFromEnd(self, head, k):
            """ :type head: ListNode :type k: int :rtype: ListNode """
            if not head or not head.next:
                return head
    
            # 先求出链表长度
            n = 0
            p = head
            while p:
                p = p.next
                n += 1
            
            # 遍历找到k的位置
            pos = 0
            p = head
            while p and k != (n - pos):
                p = p.next
                pos += 1
            return p

#### 19. [删除链表的倒数第 N 个结点][N] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2F5YW5nYW5uOTE1_size_16_color_FFFFFF_t_70 3]

删除倒数第n个节点也可以使用快慢指针的思路。

# class ListNode(object):
    # def __init__(self, val=0, next=None):
    # self.val = val
    # self.next = next
    class Solution(object):
        def removeNthFromEnd(self, head, n):
            """ :type head: ListNode :type n: int :rtype: ListNode """
            # 没有节点或者只有一个节点时直接返回
            if not head or not head.next:
                return head
            
            fast = slow = head
            # 快指针先走n步
            for i in range(n):
                fast = fast.next
    
            # pre指针用于找到倒数第n个节点的前向节点
            pre = ListNode(-1)
            while fast:
                pre.next = slow
                slow = slow.next
                fast = fast.next
                pre = pre.next
    
            pre.next = slow.next
            return head

#### 876. [链表的中间结点][Link 2] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2F5YW5nYW5uOTE1_size_16_color_FFFFFF_t_70 4]

采用的方法是先求链表长度，再求中间节点。或者快慢指针。  
感觉这道题和求倒数第n节点的思想都差不多

##### 快慢指针法 #####

快指针比慢指针多走两步，当快指针走完时，慢指针指向的节点就是中间节点

# class ListNode(object):
    # def __init__(self, x):
    # self.val = x
    # self.next = None
    
    class Solution(object):
        def middleNode(self, head):
            """ :type head: ListNode :rtype: ListNode """
            slow = fast = head
            while fast and fast.next:
                slow = slow.next
                fast = fast.next.next
            return slow

##### 先遍历再求节点 #####

# class ListNode(object):
    # def __init__(self, x):
    # self.val = x
    # self.next = None
    
    class Solution(object):
        def middleNode(self, head):
            """ :type head: ListNode :rtype: ListNode """
            n = 0
            p = head
            while p:
                p = p.next
                n += 1
    
            mid = n // 2
            p = head
            pos = 0
            while p and pos != mid:
                p = p.next
                pos += 1
            return p

#### 21. [合并两个有序链表][Link 3] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2F5YW5nYW5uOTE1_size_16_color_FFFFFF_t_70 5]

两个链表分别用指针遍历

# class ListNode(object):
    # def __init__(self, val=0, next=None):
    # self.val = val
    # self.next = next
    class Solution(object):
        def mergeTwoLists(self, l1, l2):
            """ :type l1: ListNode :type l2: ListNode :rtype: ListNode """
            fake_head = ListNode(-1)
            pre = fake_head
            while l1 and l2:
                if l1.val <= l2.val:
                    pre.next = l1
                    l1 = l1.next
                else:
                    pre.next = l2
                    l2 = l2.next
                pre = pre.next  # 写代码的时候遗漏了该指针的移动
            # 剩余节点
            pre.next = l1 or l2
            return fake_head.next

#### 141. [环形链表][Link 4] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2F5YW5nYW5uOTE1_size_16_color_FFFFFF_t_70 6]

这道题也是使用快慢指针，如果有环，快慢指针最终相遇。

快指针始终比慢指针多走一步

# class ListNode(object):
    # def __init__(self, x):
    # self.val = x
    # self.next = None
    
    class Solution(object):
        def hasCycle(self, head):
            """ :type head: ListNode :rtype: bool """
            # 加上这个判断之后时间更快了
            if not head or not head.next:
                return False
    
            fast = slow = head
            while fast and fast.next:
                slow = slow.next
                fast = fast.next.next
                # 快慢指针相遇说明存在环
                if slow == fast:
                    return True
            return False

#### 142. [环形链表 II][II 1] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2F5YW5nYW5uOTE1_size_16_color_FFFFFF_t_70 7]

这道题也使用快慢指针，只不过还需要看相遇的节点是第几个节点。

# class ListNode(object):
    # def __init__(self, x):
    # self.val = x
    # self.next = None
    
    class Solution(object):
        def detectCycle(self, head):
            """ :type head: ListNode :rtype: ListNode """
            if not head or not head.next:
                return None
            
            fast = slow = head
            while fast and fast.next:
                slow = slow.next
                fast = fast.next.next
                if slow == fast:
                    pre = head
                    while pre != slow:
                        pre = pre.next
                        slow = slow.next
                    return pre
            return None

[Link 1]: https://leetcode-cn.com/problems/reverse-linked-list/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2F5YW5nYW5uOTE1_size_16_color_FFFFFF_t_70]: /images/20221022/ffe23297debc410ea24a448eb7d6bbf4.png
[II]: https://leetcode-cn.com/problems/reverse-linked-list-ii/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2F5YW5nYW5uOTE1_size_16_color_FFFFFF_t_70 1]: /images/20221022/bd5de9de62a64a079b70df719223415b.png
[k]: https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2F5YW5nYW5uOTE1_size_16_color_FFFFFF_t_70 2]: /images/20221022/b6ba0205eb4e42ce900cadddbfa26cfc.png
[N]: https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2F5YW5nYW5uOTE1_size_16_color_FFFFFF_t_70 3]: /images/20221022/00df951165864f5c98b72db7306dce97.png
[Link 2]: https://leetcode-cn.com/problems/middle-of-the-linked-list/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2F5YW5nYW5uOTE1_size_16_color_FFFFFF_t_70 4]: /images/20221022/c3a01f600c8b434e9a118b27a254ea03.png
[Link 3]: https://leetcode-cn.com/problems/merge-two-sorted-lists/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2F5YW5nYW5uOTE1_size_16_color_FFFFFF_t_70 5]: /images/20221022/e98f823098bb4efa96b9340d1b2bdb78.png
[Link 4]: https://leetcode-cn.com/problems/linked-list-cycle/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2F5YW5nYW5uOTE1_size_16_color_FFFFFF_t_70 6]: /images/20221022/0b756553490e4cbb9d2e9fefe7fe8b30.png
[II 1]: https://leetcode-cn.com/problems/linked-list-cycle-ii/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2F5YW5nYW5uOTE1_size_16_color_FFFFFF_t_70 7]: /images/20221022/51253197a74a4fa598c6fdbbdb0cabff.png