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

链表介绍

链表（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：迭代

1. 使用两个指针 cur 和 pre 进行迭代。pre 指向 cur 前一个节点位置。初始时，pre 指向 None，cur 指向 head。

2. 将 pre 和 cur 的前后指针进行交换，指针更替顺序为：

   使用 next 指针保存当前节点 cur 的后一个节点，即 next = cur.next；

   断开当前节点 cur 的后一节点链接，将 cur 的 next 指针指向前一节点 pre，即 cur.next = pre；

   pre 向前移动一步，移动到 cur 位置，即 pre = cur；

   cur 向前移动一步，移动到之前 next 指针保存的位置，即 cur = next。

3. 继续执行第 2 步中的 1、2、3、4。

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
}

1. 硬做

2. Set

3. 快慢指针

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. 链表设计