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

链表介绍

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

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

在链表中，数据元素之间的逻辑关系是通过指针来间接反映的。逻辑上相邻的数据元素在物理地址上可能相邻，可也能不相邻。其在物理地址上的表现是随机的。 我们先来简单介绍一下链表结构的优缺点：

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

套路总结

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

精选题目

1. 反转链表

def reverseList(self, head):
cur, prev = head, None
while cur:
cur.next, prev, cur = prev, cur, cur.next
return prevfunc 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/ ​​

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