专栏首页王漂亮链表高频题
原创

链表高频题

总结:所有链表题目都做过而且都Accept了,不排除有些是抄的。。leet, leet-cn

高频共12道,另外加了两道(reverse at k和环形2)

链表定义

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

基础题

206. 反转链表

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

Solution - 递归

class Solution:
    def reverseList(self, head: ListNode):
        if not head or not head.next: return head
        
        next_node = head.next
        res = self.reverseList(next_node)
        
        next_node.next = head
        head.next = None
        
        return res

Solution - 迭代**

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

Reference 超级好

重难点 (M->H)

138. 复制带随机指针的链表

Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

Example 1:

Solution

class Node:
    def __init__(self, val, next, random):
        self.val = val
        self.next = next
        self.random = random
        
class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head: return None
        
        node = head
        di = {}
        
        while node:
            di[node] = Node(node.val, None, None)
            node = node.next
            
        node= head
        
        while node:
            di[node].next = di.get(node.next)
            di[node].random = di.get(node.random)
            node= node.next
            
        return di[head]

遍历两遍同时On哈希的空间

待优化:遍历一遍并常数空间cost

21. 合并两个有序链表

Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

Solution-递归

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        if not l1 or not l2: return l1 or l2
        
        if l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2

Solution-迭代

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        if not l1 or not l2: return l1 or l2
        
        dummy_node = ListNode(0)
        curr = dummy_node
        
        while l1 and l2:
            if l1.val <= l2.val:
                curr.next = l1
                l1 = l1.next
            else: 
                curr.next = l2
                l2 = l2.next
                
            curr = curr.next
        
        if l1 or l2: curr.next = l1 or l2
            
        return dummy_node.next

23. 合并K个排序链表

Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

Solution

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        cnt = len(lists)
        interval = 1
        while interval < cnt:
            for i in range(0, cnt-interval, interval*2):
                lists[i] = self.merge2Lists(lists[i], lists[i+interval])
            interval *= 2
            
        return lists[0] if cnt else None
    
    
    def merge2Lists(self, l1, l2):
        if not l1 or not l2:
            return l1 or l2
        
        if l1.val <= l2.val:
            l1.next = self.merge2Lists(l1.next, l2)
            return l1
        
        else:
            l2.next = self.merge2Lists(l1, l2.next)
            return l2

知道分支的思路,但mergeKLists是抄的,不知道怎么写分治的code

25. K 个一组翻转链表

Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

Example:

Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

Note:

  • Only constant extra memory is allowed.
  • You may not alter the values in the list's nodes, only nodes itself may be changed.

Solution

powcai

class Solution(object):
    def reverseKGroup(self, head, k):
        if not head or not head.next: return head
        
        cur = head
        cnt = 0
        while cur and cnt < k:
            cur = cur.next
            cnt += 1
        
        if cnt == k:
            cur = self.reverseKGroup(cur, k)
            while cnt:
                head.next, head, cur = cur, head.next, head
                cnt -= 1
            head = cur
            
        return head

双指针技巧

141. 环形链表

Given a linked list, determine if it has a cycle in it.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Solution

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        slow, fast = head, head
        
        while fast and fast.next:
            slow, fast = slow.next, fast.next.next
            
            if slow == fast: return True
            
        return False

142. 环形链表 II

Given a linked list, return the node where the cycle begins. If there is no cycle, returnnull.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1

Solution

class Solution:
    def detectCycle(self, head: ListNode):
        slow, fast = head, head
        
        while fast and fast.next:
            slow, fast = slow.next, fast.next.next
            if slow == fast: break
                
        else:
            return None
            
        while head != fast:
            head, fast = head.next, fast.next
            
        return head

160. 相交链表

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

begin to intersect at node c1.

Solution

class Solution(object):
    def getIntersectionNode(self, headA, headB):

            if not headA or not headB: return None
            from collections import defaultdict
            di = defaultdict(ListNode)
            while headA:
                di[headA] = 1
                headA = headA.next

            while headB:
                if headB in di: return headB
                headB = headB.next

            return None

Dict做法,还可以用双指针

19. 删除倒数第N个节点

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Solution

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        if not head: return None
        
        slow, fast = head, head
        
        for _ in range(n):
            fast = fast.next
        
        if not fast: return head.next
        
        while fast.next:
            slow, fast = slow.next, fast.next
            
        slow.next = slow.next.next
        
        return head

快指针先走n步

其他

234. 回文链表

Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.

Example 1:

Input: 1->2
Output: false

Example 2:

Input: 1->2->2->1
Output: true

Follow up: Could you do it in O(n) time and O(1) space?

Solution

class Solution(object):
    def isPalindrome(self, head):
        if not head: return True
        slow, fast = head, head.next
        left = []
        while fast and fast.next:
            left.append(slow.val)
            slow, fast = slow.next, fast.next.next
        
        if fast: left.append(slow.val)
        right = slow.next
            
        i = len(left)-1
        while i>=0:
            if right.val != left[i]: return False
            
            right = right.next
            i -= 1
            
        return True

328. 奇偶链表

Odd Even Linked List

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

Example 1:

Input: 1->2->3->4->5->NULL
Output: 1->3->5->2->4->NULL

Example 2:

Input: 2->1->3->5->6->4->7->NULL
Output: 2->3->6->7->1->5->4->NULL

Solution

class Solution(object):
    def oddEvenList(self, head):
        if not head or not head.next: return head

        odd = head
        even = even_head = head.next
        
        while odd and even and even.next:
            odd.next, even.next = odd.next.next, even.next.next
            odd, even = odd.next, even.next
            
        odd.next = even_head
        
        return head

2. 两数相加

Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

Solution

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        if not l1 or not l2: return l1 or l2
        
        h = res = ListNode(0)
        carry = 0
        
        while l1 or l2:
            cur_sum = 0 
            if l1:
                cur_sum += l1.val
                l1 = l1.next
            if l2:
                cur_sum += l2.val
                l2 = l2.next

            cur_sum += carry
            
            carry = 1 if cur_sum>=10 else 0
            h.next = ListNode(cur_sum%10)
            h = h.next

        if carry>0: h.next = ListNode(1)
            
        return res.next

148. 排序链表

Sort List

Sort a linked list in O(n log n) time using constant space complexity.

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4

Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5

Solution

class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        if not head or not head.next: return head
        slow, fast = head, head.next
        while fast and fast.next:
            slow, fast = slow.next, fast.next.next
        mid, slow.next = slow.next, None
        
        left, right = self.sortList(head), self.sortList(mid)
        
        # merge
        h = res = ListNode(0)
        while left and right:
            if left.val<=right.val: h.next, left = left, left.next
            else: h.next, right = right, right.next
            h = h.next
        
        h.next = left if left else right
        
        return res.next

mergesort

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 大数据小白必Get知识点!

    Hadoop 使用 HDFS 来解决分布式数据问题,MapReduce 计算范式提供有效的分布式计算。

    王脸小
  • Docker与K8S了解一下?

    https://juejin.im/post/5c98b1785188252d665f57be#heading-0

    王脸小
  • Board相关题

    Given a 2d grid map of '1's (land) and '0's (water), count the number of islands...

    王脸小
  • 数据结构基础之掌握5个常见的链表操作

    最近在重新梳理学算法的知识,本文为链表常见操作复习的总结文章,会讲解常见的链表题目实现思路及附上答案,这些题目在leetcode上对应的题号也有给出,好好学习算...

    winty
  • Python 之父的解析器系列之六:给 PEG 语法添加动作

    花下猫语:Guido 的解析器系列更新了 7 篇,他的生产力真旺盛啊。这对于新的解析器来说是件好事,但对于我来说却是个不小的挑战:需要一定的时间和精力,而我对解...

    Python猫
  • LeetCode 142:环形链表 II Linked List Cycle II

    为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。

    爱写bug
  • LeetCode 142:环形链表 II Linked List Cycle II

    为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。

    爱写bug
  • python中利用try..except来代替if..else

    在有些情况下,利用try…except来捕捉异常可以起到代替if…else的作用。 比如在判断一个链表是否存在环的leetcode题目中,初始代码是这样的

    用户7886150
  • 跟我一起学docker(13)--docker Machine的使用

    IT故事会
  • 每日一题-反转链表

    输入: 1->2->3->4->5->NULL, m = 2, n = 4 输出: 1->4->3->2->5->NULL

    程序员小王

扫码关注云+社区

领取腾讯云代金券