算法入门很简单：链表题套路及精选题目

作者：宇宙之一粟

2022 年 7 月 04 日
本文字数：3176 字
阅读完需：约 10 分钟

链表介绍

链表（Linked List）：一种线性表数据结构。它使用一组任意的存储单元（可以是连续的，也可以是不连续的），来存储一组具有相同类型的数据。

简单来说，「链表」 是实现线性表的链式存储结构的基础。存储模式如下：

在链表中，数据元素之间的逻辑关系是通过指针来间接反映的。逻辑上相邻的数据元素在物理地址上可能相邻，可也能不相邻。其在物理地址上的表现是随机的。

我们先来简单介绍一下链表结构的优缺点：

优点：存储空间不必事先分配，在需要存储空间的时候可以临时申请，不会造成空间的浪费；一些操作的时间效率远比数组高（插入、移动、删除元素等）。
缺点：不仅数据元素本身的数据信息要占用存储空间，指针也需要占用存储空间，链表结构比数组结构的空间开销大。

套路总结

链表操作套路：链表不仅仅是穿针引线，还有双指针，虚拟节点，迭代和递归。

精选题目

1. 反转链表

Python 版本：

def reverseList(self, head):    cur, prev = head, None    while cur:        cur.next, prev, cur = prev, cur, cur.next    return prev

复制代码

Go 语言版本：

func reverseList(head *ListNode) *ListNode {
    if head == nil {        return nil    }
    cur := head    var pre *ListNode
    for cur != nil {
        tmp := cur.Next        cur.Next = pre        pre = cur        cur = tmp    }    return pre}

复制代码

2. 反转链表 2

https://leetcode-cn.com/problems/reverse-linked-list-ii/

思路 1：迭代

使用两个指针 cur 和 pre 进行迭代。pre 指向 cur 前一个节点位置。初始时，pre 指向 None，cur 指向 head。
将 pre 和 cur 的前后指针进行交换，指针更替顺序为：
使用 next 指针保存当前节点 cur 的后一个节点，即 next = cur.next；
断开当前节点 cur 的后一节点链接，将 cur 的 next 指针指向前一节点 pre，即 cur.next = pre；
pre 向前移动一步，移动到 cur 位置，即 pre = cur；
cur 向前移动一步，移动到之前 next 指针保存的位置，即 cur = next。
继续执行第 2 步中的 1、2、3、4。
最后等到 cur 遍历到链表末尾，即 cur == None，时，pre 所在位置就是反转后链表的头节点，返回新的头节点 pre。

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

复制代码

思路 2：递归

具体做法如下：

首先定义递归函数含义为：将链表反转，并返回反转后的头节点。
然后从 head.next 的位置开始调用递归函数，即将 head.next 为头节点的链表进行反转，并返回该链表的头节点。
递归到链表的最后一个节点，将其作为最终的头节点，即为 new_head。
在每次递归函数返回的过程中，改变 head 和 head.next 的指向关系。也就是将 head.next 的next 指针先指向当前节点 head，即 head.next.next = head 。
然后让当前节点 head 的 next 指针指向 None，从而实现从链表尾部开始的局部反转。
当递归从末尾开始顺着递归栈的退出，从而将整个链表进行反转。
最后返回反转后的链表头节点 new_head。

class Solution:    def reverseList(self, head: ListNode) -> ListNode:        if head == None or head.next == None:            return head        new_head = self.reverseList(head.next)        head.next.next = head        head.next = None        return new_head

复制代码

3. 两数相加

def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
    dummy = tail = ListNode(None)    sum = 0    while l1 or l2 or sum:        sum += (l1.val if l1 else 0) + (l2.val if l2 else 0)        tail.next = ListNode(sum % 10)        tail = tail.next        sum // 10        l1 = l1.next if l1 else None        l2 = l2.next if l2 else None    return dummy.next

复制代码

4. 两两交换链表中的节点

def swapPairs(self, head: ListNode) -> ListNode:    # 申请一个虚节点头    pre, pre.next = self, head
    # 空 或者 只剩下一个节点    while pre.next and pre.next.next:        a = pre.next        b = a.next
        pre.next, b.next, a.next = b, a, b.next        pre = a
    return pre.next

复制代码

func swapPairs(head *ListNode) *ListNode {    if head == nil {        return nil    }    if head.Next == nil {        return head    }
    var (        dummy *ListNode = &ListNode{0, head}        temp = dummy        cur = dummy.Next    )
    for cur != nil && cur.Next != nil {        temp.Next = cur.Next        cur.Next = cur.Next.Next        temp.Next.Next = cur                temp = cur        cur = cur.Next    }    return dummy.Next}

复制代码

5. 环形链表--判断是否有环

func hasCycle(head *ListNode) bool {    first, second := head, head    for first != nil && first.Next != nil {        first = first.Next.Next        second = second.Next        if first == second {            return true        }    }    return false}

复制代码

硬做
Set
快慢指针

def hasCycle(self, head):    fast = slow = head    while slow and fast and fast.next:        slow = slow.next        fast = fast.next.next        if slow is fast:            return True    return False

复制代码

6. 环型链表 2

7. K 个一组翻转链表

优先队列

class Solution:    # 翻转一个子链表，并且返回新的头与尾    def reverse(self, head: ListNode, tail: ListNode):        prev = tail.next        p = head        while prev != tail:            nex = p.next            p.next = prev            prev = p            p = nex        return tail, head
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:        hair = ListNode(0)        hair.next = head        pre = hair
        while head:            tail = pre            # 查看剩余部分长度是否大于等于 k            for i in range(k):                tail = tail.next                if not tail:                    return hair.next            nex = tail.next            head, tail = self.reverse(head, tail)            # 把子链表重新接回原链表            pre.next = head            tail.next = nex            pre = tail            head = tail.next                return hair.next

复制代码

func reverseKGroup(head *ListNode, k int) *ListNode {    hair := &ListNode{Next: head}    pre := hair
    for head != nil {        tail := pre        for i := 0; i < k; i++ {            tail = tail.Next            if tail == nil {                return hair.Next            }        }        nex := tail.Next        head, tail = myReverse(head, tail)        pre.Next = head        tail.Next = nex        pre = tail        head = tail.Next    }    return hair.Next}
func myReverse(head, tail *ListNode) (*ListNode, *ListNode) {    prev := tail.Next    p := head    for prev != tail {        nex := p.Next        p.Next = prev        prev = p        p = nex    }    return tail, head}

复制代码

8. 插入排序

9. 链表排序

https://leetcode-cn.com/problems/sort-list/

10. 链表设计

发布于: 刚刚阅读数: 4

原文链接:【http://xie.infoq.cn/article/20c364729a8c695355593ccab】。文章转载请联系作者。

宇宙之一粟

关注

宇宙古今无有穷期，一生不过须臾，当思奋争 2020.05.07 加入

🏆InfoQ写作平台-第二季签约作者 🏆 混迹于江湖，江湖却没有我的影子热爱技术，专注于后端全栈，轻易不换岗拒绝内卷，工作于软件工程师，弹性不加班热衷分享，执着于阅读写作，佛系不水文

发布

暂无评论

创作场景

算法入门很简单：链表题套路及精选题目

链表介绍

套路总结

精选题目

1. 反转链表

2. 反转链表 2

思路 1：迭代

思路 2：递归

3. 两数相加

4. 两两交换链表中的节点

5. 环形链表--判断是否有环

6. 环型链表 2

7. K 个一组翻转链表

8. 插入排序

9. 链表排序

10. 链表设计

宇宙之一粟

评论