链表介绍
链表（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
思路 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 }
