链表高频题

总结:所有链表题目都做过而且都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 条评论
登录 后参与评论

相关文章

来自专栏front-end technology

使用vue技术栈,作为一个前端架构师是必须掌握这些知识点的

一.对于mvvm的理解 1.MVVM 是 Model-View-ViewModel 的缩写 2.Model代表数据模型,也可以在Model中定义数据修改和操作的...

22440
来自专栏彤哥读源码

死磕 java同步系列之zookeeper分布式锁

zooKeeper是一个分布式的,开放源码的分布式应用程序协调服务,它可以为分布式应用提供一致性服务,它是Hadoop和Hbase的重要组件,同时也可以作为配置...

8300
来自专栏Java架构学习路线

8种创建Java线程的方式,你知道几个?

创建线程,是多线程编程中最基本的操作,彤哥总结了一下,大概有8种创建线程的方式,你知道吗?

8600
来自专栏彤哥读源码

死磕 java线程系列之创建线程的8种方式

创建线程,是多线程编程中最基本的操作,彤哥总结了一下,大概有8种创建线程的方式,你知道吗?

6600
来自专栏好好学java的技术栈

面试官:Logback如何配置,才能提升TPS?

SpringBoot工程自带logback和slf4j的依赖,所以重点放在编写配置文件上,需要引入什么依赖,日志依赖冲突统统都不需要我们管了。logback框架...

9140
来自专栏sktj

javascript 基础知识

var bs=Array(); var bs=[1,2,3,4] bs[0]=1 for(i=0;i<bs.length;i++)

6600
来自专栏算法与编程之美

Java如何实现单链表

数据结构在计算机科学中是一门综合性的专业基础课,因此对于它的理解是很重要。数据的储存结构分为顺序存储结构和链式存储结构。前一种存储结构则需要在内存中使用一块连续...

14700
来自专栏AI科技大本营的专栏

简单粗暴上手TensorFlow 2.0,北大学霸力作,必须人手一册!

这是一本简明的 TensorFlow 2.0 入门指导手册,基于 Keras 和 Eager Execution(即时运行)模式,力图让具备一定机器学习及 Py...

15640
来自专栏Jerry的SAP技术分享

SAP云平台里的三叉戟应用

海皇波塞冬(Poseidon),奥林匹斯十二神中地位仅次于宙斯的大神,海界的统治者,他的威严与大地无穷无尽的生命力及洪水相匹敌。三叉戟是海皇波塞冬的武器,外型似...

6500
来自专栏媒矿工厂

OMAF4CLOUD:启用标准的360°视频创建服务

原标题:OMAF4CLOUD: STANDARDS-ENABLED 360° VIDEO CREATION AS A SERVICE

19400

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励