「57」算法(二) → 链表

发表于 更新于 本文字数： 1.1k 阅读时长 ≈ 1 分钟
  • 反转单向链表
    • 反转单向链表的[N,M]
  • 删除链表重复元素
  • 合并两个有序链表
  • 旋转链表
  • 排序链表
  • 两数相加
    …

反转单向链表

要求

1
2
3
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

思路分析：

变量暂存替换法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func ReserveList(head *ListNode) *ListNode {
	if head == nil || head.next == nil {
		return head
	}
	var pre *ListNode
	for head != nil {
        // 简化版：
        // head, head.next, pre = head.next, pre, head
		nextNode := head.next
		head.next = pre
		pre = head
		head = nextNode
	}
	return pre
}
双头指针法

1
2
3
4
5
6
7
8
9
10
11
12
13
func ReserveList(head *ListNode) *ListNode {
	if head == nil || head.next == nil {
		return head
	}
	cur := head
	for head.next != nil {
		tmp := head.next.next
		head.next.next = cur
		cur = head.next
		head.next = tmp
	}
	return cur
}

反转单向链表前N个

要求：

思路：

coding:

1
2
3
4
5
6
7
8
9
10
11
12
13
var nochange *ListNode

func ReserveListN(head *ListNode, n int) *ListNode {

	if n == 1 {
		nochange = head.next
		return head
	}
	last := ReserveListN(head.next, n-1)
	head.next.next = head
	head.next = nochange
	return last
}

反转单向链表N~M之间的

要求：

思路：

coding:

1
2
3
4
5
6
7
8
9
//翻转[N,M]范围内的元素
func ReserveListNM(head *ListNode, n, m int) *ListNode {

	if n == 1 {
		return ReserveListN(head, m)
	}
	head.next = ReserveListNM(head.next, n-1, m-1)
	return head
}

待更新…