4.4 反转链表

Kesa...大约 5 分钟

4.4.1 问题24: 反转链表

给定单链表的头节点 head ，请反转链表，并返回反转后的链表的头节点。
示例 1：
img
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：
img
输入：head = [1,2]
输出：[2,1]
示例 3：
输入：head = []
输出：[]
提示：
链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000
**进阶：**链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

4.4.1.1 分析

反转一个节点, 需要三个指针:

当前节点
前一个节点
后一个节点

4.4.1.2 题解

func reverseList(head *ListNode) *ListNode {
	var prev *ListNode
	cur := head
	for cur != nil {
		next := cur.Next
		// 反转
		cur.Next = prev
		// 更新
		prev = cur
		cur = next
	}

	return prev
}

4.4.2 问题25: 链表中的数字相加

LCR 025. 两数相加 IIopen in new window

给定两个 非空链表 l1和 l2 来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
可以假设除了数字 0 之外，这两个数字都不会以零开头。
示例1：
img
输入：l1 = [7,2,4,3], l2 = [5,6,4]
输出：[7,8,0,7]
示例2：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[8,0,7]
示例3：
输入：l1 = [0], l2 = [0]
输出：[0]
提示：
链表的长度范围为 [1, 100]
0 <= node.val <= 9
输入数据保证链表代表的数字无前导 0

4.4.2.1 分析

如果直接将链表数字转换成整型, 那么可能会溢出, 此时无法计算.

按照十进制的计算规则, 数位对齐后从个位开始计算. 那么需要先将链表反转, 然后从首位开始计算.

4.4.2.2 题解

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	// 反转链表
	rl1 := reverseList25(l1)
	rl2 := reverseList25(l2)
	// 按位计算
	res := addList(rl1, rl2)

	return reverseList25(res)
}

func reverseList25(head *ListNode) *ListNode {
	var prev *ListNode
	cur := head
	for cur != nil {
		next := cur.Next
		cur.Next = prev
		prev = cur
		cur = next
	}

	return prev
}

func addList(l1, l2 *ListNode) *ListNode {
	dummy := &ListNode{}

	carry := 0 // 进位
	node := dummy
	for l1 != nil || l2 != nil {
		sum := 0
		sum += getVal(l1) + getVal(l2) + carry
		if sum >= 10 {
			carry = 1
		} else {
			carry = 0
		}

		// 记录结果
		v := sum % 10
		node.Next = &ListNode{Val: v}
		node = node.Next

		if l1 != nil {
			l1 = l1.Next
		}
		if l2 != nil {
			l2 = l2.Next
		}
	}

	if carry == 1 {
		node.Next = &ListNode{Val: 1}
	}

	return dummy.Next
}

func getVal(node *ListNode) int {
	if node == nil {
		return 0
	}
	return node.Val
}

4.4.3 问题26: 重排链表

LCR 026. 重排链表open in new window

给定一个单链表 L 的头节点 head ，单链表 L 表示为：
L0 → L1 → … → Ln-1 → Ln 请将其重新排列后变为：
L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1:
img
输入: head = [1,2,3,4]
输出: [1,4,2,3]
示例 2:
img
输入: head = [1,2,3,4,5]
输出: [1,5,2,4,3]
提示：
链表的长度范围为 [1, 5 * 104]
1 <= node.val <= 1000

4.4.3.1 分析

问题实际上是将链表分为前后两半, $l_1: [n_1, n_2, ..., n_i]$ 和 $l_2: [n_{i+1}, n_{i+2}, ... n_n]$ ;

链表长度为:

偶数时, $l_1, l_2$ 长度相同
奇数时, $l_1$ 比 $l_2$ 多一个元素

然后将 $l_2$ 反转后插入 $l_1$ 中.

将链表拆分成两半, 使用快慢指针来寻找中间节点:

快指针每次移动两个节点
慢指针每次移动一个节点

当快指针到达尾节点时, 慢指针在链表的中间节点.

4.4.3.2 题解

func reorderList(head *ListNode) {
	// 快慢指针, 寻找中间节点
	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next
		if fast.Next != nil {
			fast = fast.Next
		}
	}

	// 分离前后半链表
	tmp := slow.Next
	slow.Next = nil

	link(head, reverseList26(tmp))
}

func reverseList26(head *ListNode) *ListNode {
	var prev *ListNode
	cur := head
	for cur != nil {
		next := cur.Next
		cur.Next = prev

		prev = cur
		cur = next
	}

	return prev
}

func link(node1, node2 *ListNode) {
	dummy := &ListNode{}
	
	node := dummy
	for node1 != nil && node2 != nil {
		tmp := node1.Next

		node.Next = node1
		node1.Next = node2
		node = node2

		node1 = tmp
		node2 = node2.Next
	}
	if node1 != nil {
		node.Next = node1
	}
}

4.4.4 问题27: 回文链表

LCR 027. 回文链表open in new window

给定一个链表的 头节点 head **，**请判断其是否为回文链表。
如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。
示例 1：
输入: head = [1,2,3,3,2,1]
输出: true
示例 2：
输入: head = [1,2]
输出: false
提示：
链表 L 的长度范围为 [1, 105]
0 <= node.val <= 9

4.4.4.1 分析

对于回文链表来说, 若将其分为前后两半链表 $l_1, l_2$ :

链表长度为偶数: $l_1$ 和反转后的 $l_2$ 是相同的
链表长度为奇数: 不包含中间节点( $l_1$ 去除最后一个节点) 和 $l_2$ 的反转是相同的

时间复杂度: O(n)

空间复杂度: O(1)

4.4.4.2 题解

func isPalindrome(head *ListNode) bool {
	// 边界条件
	if head == nil || head.Next == nil {
		return true
	}

	dummy := &ListNode{Next: head}
	// 快慢双指针, 寻找中间节点
	slow, fast := dummy, dummy.Next
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}

	// 前半部分
	secondHalf := &ListNode{}
	if fast == nil {
		secondHalf = slow.Next
	} else if fast.Next == nil { // 链表长为奇数
		secondHalf = slow.Next.Next
	}

	// 前后分离
	slow.Next = nil
	// 反转后半
	secondHalf = reverseList27(secondHalf)
	// 比较
	return listEqual(head, secondHalf)
}

func reverseList27(head *ListNode) *ListNode {
	var prev *ListNode
	cur := head
	for cur != nil {
		next := cur.Next

		cur.Next = prev

		prev = cur
		cur = next
	}

	return prev
}

func listEqual(head1, head2 *ListNode) bool {
	for head1 != nil && head2 != nil {
		if head1.Val != head2.Val {
			return false
		}

		head1 = head1.Next
		head2 = head2.Next
	}

	return head1 == nil && head2 == nil
}

Reference

剑指Offer（专项突破版）open in new window

昵称

邮箱

网址

按正序
按倒序
按热度

4.4 反转链表

# 4.4.1 问题24: 反转链表

# 4.4.1.1 分析

# 4.4.1.2 题解

# 4.4.2 问题25: 链表中的数字相加

# 4.4.2.1 分析

# 4.4.2.2 题解

# 4.4.3 问题26: 重排链表

# 4.4.3.1 分析

# 4.4.3.2 题解

# 4.4.4 问题27: 回文链表

# 4.4.4.1 分析

# 4.4.4.2 题解

# Reference

预览: