06-链表相关高频题总结.md

[TOC]
# 1 链表问题

> 面试时链表解题的方法论

> 对于笔试，不用太在乎空间复杂度，一切为了时间复杂度

> 对于面试，时间复杂度依然放在第一位，但是一定要找到空间最省的方法

## 1.1 链表面试常用数据结构和技巧

1、 使用容器（哈希表，数组等）

2、 快慢指针

### 1.1.1 快慢指针问题

1、 输入链表头结点，奇数长度返回中点，偶数长度返回上中点

> 1 3 5 2 7 返回 5；1 3 2 7 返回 3

2、 输入链表头结点，奇数长度返回中点，偶数长度返回中下点

> 1 3 5 2 7 返回 5；1 3 2 7 返回 2

3、 输入链表头结点，奇数长度返回中点前一个，偶数长度返回上中点前一个

> 1 3 5 2 7 返回 3；1 3 2 7 返回 1

4、 输入链表头结点，奇数长度返回中点前一个，偶数长度返回下中点前一个

> 1 3 5 2 7 返回 3；1 3 2 7 返回 3

```Go
package main

import "fmt"

type Node struct {
	Val  int
	Next *Node
}

// NewLinkedList 初始化一个链表 返回链表的头结点
func NewLinkedList(val int) (head *Node) {
	return &Node{
		Val:  val,
		Next: nil,
	}
}

// MidOrUpMidNode 给定一个链表的头节点
// 1. 奇数长度返回中点, 偶数长度返回上中点
func (head *Node) MidOrUpMidNode() *Node {
	// 该链表没有点，有一个点，有两个点的时候都是返回头结点
	if head == nil || head.Next == nil || head.Next.Next == nil {
		return head
	}

	// 链表有3个点或以上
	// 快慢指针，快指针一次走两步，慢指针一次走一步
	// 快指针走完，慢指针在中点位置
	slow := head.Next
	fast := head.Next.Next
	for fast.Next != nil && fast.Next.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}
	return slow
}

// MidOrDownMidNode 给定一个链表的头节点
// 2、奇数长度返回中点，偶数长度返回中下点
func (head *Node) MidOrDownMidNode() *Node {
	// 该链表没有点，有一个点, 返回头结点
	if head == nil || head.Next == nil {
		return head
	}
	slow := head.Next
	fast := head.Next
	for fast.Next != nil && fast.Next.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}
	return slow
}

// MidOrUpMidPreNode 给定一个链表的头节点
// 3、奇数长度返回中点前一个，偶数长度返回上中点前一个
func (head *Node) MidOrUpMidPreNode() *Node {
	// 该链表没有点，有一个点, 有两个点， 返回头结点
	if head == nil || head.Next == nil || head.Next.Next == nil {
		return nil
	}
	slow := head
	fast := head.Next.Next
	for fast.Next != nil && fast.Next.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}
	return slow
}

// MidOrDownMidPreNode 给定一个链表的头节点
// 4、奇数长度返回中点前一个，偶数长度返回下中点前一个
func (head *Node) MidOrDownMidPreNode() *Node {
	if head == nil || head.Next == nil {
		return nil
	}
	if head.Next.Next == nil {
		return head
	}
	slow := head
	fast := head.Next
	for fast.Next != nil && fast.Next.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}
	return slow
}

func main() {
	// 0 1
	// 0 1 2
	// 0 1 2 3
	// 0 1 2 3 4
	// 0 1 2 3 4 5
	// 0 1 2 3 4 5 6
	// 0 1 2 3 4 5 6 7
	// 0 1 2 3 4 5 6 7 8
	hd := &Node{}
	hd.Next = &Node{Val: 1}
	hd.Next.Next = &Node{Val: 2}
	hd.Next.Next.Next = &Node{Val: 3}
	hd.Next.Next.Next.Next = &Node{Val: 4}
	hd.Next.Next.Next.Next.Next = &Node{Val: 5}
	hd.Next.Next.Next.Next.Next.Next = &Node{Val: 6}
	hd.Next.Next.Next.Next.Next.Next.Next = &Node{Val: 7}
	// hd.Next.Next.Next.Next.Next.Next.Next.Next = &Node{Val: 8}

	ans1 := hd.MidOrUpMidNode()
	fmt.Println(fmt.Sprintf("1.奇数长度返回中点，偶数长度返回上中点: %d", ans1.Val))
	ans2 := hd.MidOrDownMidNode()
	fmt.Println(fmt.Sprintf("2.奇数长度返回中点，偶数长度返回中下点: %d", ans2.Val))
	ans3 := hd.MidOrUpMidPreNode()
	fmt.Println(fmt.Sprintf("3.奇数长度返回中点前一个，偶数长度返回上中点前一个: %d", ans3.Val))
	ans4 := hd.MidOrDownMidPreNode()
	fmt.Println(fmt.Sprintf("4.奇数长度返回中点前一个，偶数长度返回下中点前一个: %d", ans4.Val))
}
```

### 1.1.2 面试题一：判断回文结构

> 给定一个单链表的头结点head，请判断该链表是否为回文结构。回文就是正着输出和反着输出结果一样

1. 栈的方法特别简单（笔试用）

> 笔试思路，以此把该链表放入栈中。再遍历该链表和栈中弹出的数比对，只要有不一样，就不是回文

2. 改原链表的方法需要注意边界问题（面试用）

> 快慢指针解法：用快慢指针定位到中点的位置，奇数就是定位到唯一的中点，偶数定位到上中点。然后把中点右半部分加入栈中去，那么栈中存的是右半部分的逆序。接着从头遍历链表，栈中有多少个元素，我们就比较多少步，如果有对不上就不是回文

> 快慢指针最优解，不使用容器结构(stack)，O(1)：同样的找到中点位置，把右半部分指针回指到中点。接着指针1从L位置，指针2从R位置，往中间遍历。，每步比对，如果有不一样，则不是回文。返回答案之前，把中点右边的指针调整回来

```Go
package main

// 判断一个链表是否是回文链表
// 解法1：遍历链表，把链表放入一个数组中，倒序遍历数组切片，和正序遍历数组切片依次对比，都相等即为回文，实现略
// 解法2：遍历链表，按照快慢指针使慢指针定位到链表的中点位置，依次把慢指针指向的值写入数组切片中，此时数组中保存着链表前一半的元素。
//			且slow的位置是链表的中间位置。按倒序遍历数组切片，与按slow位置顺序遍历链表的元素依次对比，如果都相等，则为回文。实现略
// 解法2比解法1省了一半的空间，解法一空间复杂度O(n)，解法2空间复杂度为O(n/2)
// 解法3：不使用额外空间，空间复杂度为O(1)

type Node struct {
	Val  int
	Next *Node
}

// IsPalindrome 给定链表头节点，判断该链表是不是回文链表。空间复杂度为O(1)
func (head *Node) IsPalindrome() bool {
	// 链表为空，或者链表只有一个节点，是回文结构
	if head == nil || head.Next == nil {
		return true
	}
	// 慢指针
	slow := head
	// 快指针
	fast := head
	for fast.Next != nil && fast.Next.Next != nil { // 循环结束，slow停在链表中点位置
		slow = slow.Next
		fast = fast.Next.Next
	}

	fast = slow.Next // 快指针回到中点的下一个节点，之后快指针将从每次走两步，变为每次走一步
	slow.Next = nil // 从中点截断链表，mid.next -> nil
	var tmp *Node
	// 对原链表右半部分，进行逆序，逆序后，从原尾节点指向中点
	for fast != nil {
		tmp = fast.Next // tmp暂时保存fast的下一个节点
		fast.Next = slow // 翻转链表指向
		slow = fast // slow 移动
		fast = tmp // fast 移动
	}

	// tmp指针记录最后的位置，之后把右半部再逆序回原来的次序
	tmp = slow
	fast = head
	var res = true
	for slow != nil && fast != nil { // 原链表的左右部门进行回文对比
		if slow.Val != fast.Val {
			res = false
			break
		}
		slow = slow.Next // 从原链表头节点，往原链表中间节点移动
		fast = fast.Next // 从原链表尾节点，往原链表中间节点移动
	}
	slow = tmp.Next
	tmp.Next = nil
	// 把原链表右半部分再逆序回来
	for slow != nil {
		fast = slow.Next
		slow.Next = tmp
		tmp = slow
		slow = fast
	}
	// 返回回文的判断结果 true
	return res
}
```

### 1.1.3 面试题三

> 一种特殊的单链表结构如下：

```Go
type CopyLinkedListNode struct {
	Val int
	Next *CopyLinkedListNode
	Rand *CopyLinkedListNode
}
```

> rand指针是单链表节点结构中新增加的指针，rand可能指向链表中的任意一个节点，也可能为null。给定一个由Node节点类型组成的无环单链表节点head。请实现一个函数完成这个链表的复制，并返回复制的新链表的头结点。

> 要求时间复杂度为O(N)，额外空间复杂度为O(1)

1. 哈希表方法(笔试推荐)

> 第一步遍历，把所有节点加入到Map<Node, Node>表示老节点到克隆出来的节点映射

> 第二步遍历，查map找到克隆节点，最后返回头结点

2. 不用哈希表的方法，人为构造对应关系(面试推荐)

> 第一步：每个节点遍历的时候克隆出来一个新的节点加入到当前节点和其next节点的中间

> 第二步：此时经过第一步所有节点和其克隆节点都是串在一起的，依次拿出当前节点和其克隆节点，当前节点的rand指针指向的节点的克隆节点给当前节点克隆的节点的rand节点指向的节点。

> 第三步：此时老节点的rand指针没变化，克隆节点的rand指针也都指向了对应的克隆节点。此时在大的链表上分离出来原链表和克隆链表

```Go
package main

type CopyLinkedListNode struct {
	Val int
	Next *CopyLinkedListNode
	Rand *CopyLinkedListNode
}

// 方法1
func (head *CopyLinkedListNode) copyListWithRand1() *CopyLinkedListNode {
	m := make(map[*CopyLinkedListNode]*CopyLinkedListNode)
	cur := head
	for cur != nil {
		// 当前节点，克隆出来一个相同值的新节点加入map中
		m[cur] = &CopyLinkedListNode{Val: cur.Val}
		cur = cur.Next
	}
	// 当前节点从头开始
	cur = head
	for cur != nil {
		// cur原节点，m[cur]是新节点
		m[cur].Next = m[cur.Next]
		m[cur].Rand = m[cur.Rand]
		cur = cur.Next
	}
	// 返回原头结点的映射，也就是克隆链表的头结点
	return m[head]
}

// 方法2
func (head *CopyLinkedListNode) copyListWithRand2() *CopyLinkedListNode {
	if head == nil {
		return head
	}
	cur := head
	var next *CopyLinkedListNode = nil
	// 克隆出来的node放在原本node和next指向的node中间
	// 1 -> 2
	// 1 -> 1' -> 2
	for cur != nil {
		// cur 老节点   next 老的下一个节点
		next = cur.Next
		cur.Next = &CopyLinkedListNode{Val: cur.Val}
		cur.Next.Next = next
		cur = next
	}
	cur = head
	var curCopy *CopyLinkedListNode = nil
	// set copy node rand
	// 1 -> 1' -> 2 -> 2'
	// 设置新的克隆节点间的rand节点
	for cur != nil {
		// cur 老节点
		// cur.next => 新的 copy出来的节点
		next = cur.Next.Next
		curCopy = cur.Next
		if cur.Rand != nil {
			curCopy.Rand = cur.Rand.Next
		} else {
			curCopy.Rand = nil
		}
		cur = next
	}
	// 老的头结点：head 新克隆出来的头结点： head.next
	res := head.Next
	cur = head
	// split，分离原本节点组成的链表和克隆节点组成的链表
	for cur != nil {
		next = cur.Next.Next
		curCopy = cur.Next
		cur.Next = next
		if next != nil {
			curCopy.Next = next.Next
		} else {
			curCopy.Next = nil
		}
		cur = next
	}
	return res
}
```

### 1.1.4 面试题四

> 该问题和约舍夫环问题是链表问题的比较难的问题

> 题目描述：给定两个可能有环也可能无环的单链表，头结点head1和head2。请实现一个函数，如果两个链表相交，请返回相交的第一个节点。如果不相交，返回null

> 要求：如果两个链表长度之和为N，时间复杂度请达到O(N)，额为空间复杂度请达到O(1)

> 思路：由于是单链表，则一旦成环就结束，出不来，因为每个节点只有一个Next指针

1. 方法一：用set把每个节点的内存地址放到set里面，如果存在相同的内存在set中存在，则就是第一个成环的节点


2. 方法二：用快慢指针对链表遍历，那么快慢指针一定会相遇，能相遇就说明存在环。然后让慢指针停在相遇的位置，快指针回到头结点。快指针和慢指针再出发且快指针也变成一次走一步和满指针相同，再次相遇的节点就是成环节点

```Go
package main

import (
	"fmt"
	"math"
)

type Node struct {
	Val  int
	Next *Node
}

// GetIntersectNode 给定两个链表的头节点，判断两个链表是否相交，如果两个链表相交，请返回相交的第一个节点，不相交则返回nil
func GetIntersectNode(head1, head2 *Node) *Node {
	if head1 == nil || head2 == nil {
		return nil
	}
	// head1的第一个入环节点
	loop1 := head1.GetLoopNode()
	// head2的第一个入环节点
	loop2 := head2.GetLoopNode()
	// 两个无环链表是否相交的情况
	// 由于每个节点只有一个next指针，则如果两个无环相交则相交之后就只剩下公共部分
	// 方法1把第一条链表放到set中，第二个链表依次查在不在该set中，第一个找到的就是
	// 方法2
	// 把链表1走到尾结点end1，记录长度l1
	// 把链表1走到尾结点end2，记录长度l2
	// 如果end1和end2的内存地址不同一定不相交
	// 如果end1==end2，则(1)长的链表从头结点先走保证和短链表相同长度的位置，再以此往下走，第一次相同节点
	// (2)则依次从尾结点出发，找第一次出现内存地址不相同的那个节点，该节点的next节点就是第一次相交的节点
	if loop1 == nil && loop2 == nil {
		return NoLoop(head1, head2)
	}
	// 一个为空，另外一个不为空不可能相交。两个都不为空的情况下共用一个环
	if loop1 != nil && loop2 != nil {
		return BothLoop(head1, loop1, head2, loop2)
	}
	return nil
}

// GetLoopNode 给定一个链表头节点，找到链表第一个入环节点，如果无环，返回nil
func (head *Node) GetLoopNode() *Node {
	// 少于三个节点，无环
	if head == nil || head.Next == nil || head.Next.Next == nil {
		return nil
	}
	idx1 := head.Next      // idx1 为慢指针下标
	idx2 := head.Next.Next // idx2 为快指针下标
	for idx1 != idx2 {
		if idx2.Next == nil || idx2.Next.Next == nil {
			return nil
		}
		idx2 = idx2.Next.Next
		idx1 = idx1.Next
	}
	// idx1 == idx2 相遇。快指针回到开头，满指针停在原地
	idx2 = head
	for idx1 != idx2 {
		// 此时快慢指针每次移动相同步数
		idx1 = idx1.Next
		idx2 = idx2.Next
	}
	// 再次相遇的点，即为成环的点
	return idx1
}

// NoLoop 给定两个无环链表的头节点, 如果相交返回相交节点，如果不想交返回nil
func NoLoop(head1, head2 *Node) *Node {
	if head1 == nil || head2 == nil {
		return nil
	}
	cur1 := head1
	cur2 := head2
	n := 0
	// 遍历链表1，记录节点个数
	for cur1.Next != nil {
		n++
		cur1 = cur1.Next
	}
	// 遍历链表2，记录节点个数
	for cur2.Next != nil {
		n--
		cur2 = cur2.Next
	}
	// 由于是单链表，所以如果两个无环链表相交，必定是从相交的点往后，为公共部分,类似这种形状：
	// ------------------------->
	//       1 2 3 4
	//               5 7 8 9 6 3
	// 2 5 8 2 4 5 7
	if cur1 != cur2 { // 遍历完两个链表，如果有环进入公共部分，所以cur1和cur2必定地址相同
		return nil
	}
	// n绝对值此时为  :  链表1长度减去链表2长度的值
	// 谁长，谁的头变成cur1,谁短，谁的头节点变为cur2
	if n > 0 { // 链表1 长
		cur1 = head1
		cur2 = head2
	} else { // 链表2长或两个链表相等
		cur1 = head2
		cur2 = head1
	}
	// 取n的绝对值
	n = int(math.Abs(float64(n)))
	for n != 0 { // 长链表，先走到差值位置。此时长短链表剩余的长度相等
		n--
		cur1 = cur1.Next
	}

	for cur1 != cur2 { // 两个链表共同向下移动，一旦地址相等，即为第一个相交的节点
		cur1 = cur1.Next
		cur2 = cur2.Next
	}
	return cur1
}

// BothLoop 两个有环链表，返回第一个相交节点，如果不想交返回nil
//  head1的入环节点是loop1，head2的入环节点是loop2
func BothLoop(head1, loop1, head2, loop2 *Node) *Node {
	var cur1 *Node = nil
	var cur2 *Node = nil
	// 类似第一种都无环的情况
	// 由于是单链表，那么最终成环的是两个链表的公共部门
	// ---------------------------------------->
	//       1 2 3 4
	//
	//               5 7 8 9 6 3 4 5 7 8
	// 							   3   9
	//								 7
	// 2 5 8 2 4 5 7
	if loop1 == loop2 { // 情况1： 公共部分在成环前
		cur1 = head1
		cur2 = head2
		n := 0
		for cur1 != loop1 {
			n++
			cur1 = cur1.Next
		}
		for cur2 != loop2 {
			n--
			cur2 = cur2.Next
		}
		// 谁长，谁的头变成cur1,谁短，谁的头节点变为cur2
		if n > 0 { // 链表1 长
			cur1 = head1
			cur2 = head2
		} else { // 链表2长或两个链表相等
			cur1 = head2
			cur2 = head1
		}
		// 取n的绝对值
		n = int(math.Abs(float64(n)))
		for n != 0 { // 长链表，先走到差值位置。此时长短链表剩余的长度相等
			n--
			cur1 = cur1.Next
		}
		for cur1 != cur2 { // 两个链表共同向下移动，一旦地址相等，即为第一个相交的节点
			cur1 = cur1.Next
			cur2 = cur2.Next
		}
		return cur1
	} else { // 情况2： 公共部门在环内。
		// 找第一个成环节点转回自身的过程中遇到loop2, 则相交，否则不相交
		cur1 = loop1.Next
		for cur1 != loop1 { // 链表1沿着成环节点转一圈
			if cur1 == loop2 {
				return loop1
			}
			cur1 = cur1.Next
		}
		return nil
	}
}

func main() {
	// 1->2->3->4->5->6->7->null
	head1 := &Node{Val: 1}
	head1.Next = &Node{Val: 2}
	head1.Next.Next = &Node{Val: 3}
	head1.Next.Next.Next = &Node{Val: 4}
	head1.Next.Next.Next.Next = &Node{Val: 5}
	head1.Next.Next.Next.Next.Next = &Node{Val: 6}
	head1.Next.Next.Next.Next.Next.Next = &Node{Val: 7}

	// 0->9->8->6->7->null
	head2 := &Node{Val: 0}
	head2.Next = &Node{Val: 9}
	head2.Next.Next = &Node{Val: 8}
	head2.Next.Next.Next = head1.Next.Next.Next.Next.Next // 8 -> head1(6)
	fmt.Println(GetIntersectNode(head1, head2))

	// 1->2->3->4->5->6->7->4...
	head1 = &Node{Val: 1}
	head1.Next = &Node{Val: 2}
	head1.Next.Next = &Node{Val: 3}
	head1.Next.Next.Next = &Node{Val: 4}
	head1.Next.Next.Next.Next = &Node{Val: 5}
	head1.Next.Next.Next.Next.Next = &Node{Val: 6}
	head1.Next.Next.Next.Next.Next.Next = &Node{Val: 7}
	head1.Next.Next.Next.Next.Next.Next.Next = head1.Next.Next.Next // 7 -> head1(4)

	// 0->9->8->2...
	head2 = &Node{Val: 0}
	head2.Next = &Node{Val: 9}
	head2.Next.Next = &Node{Val: 8}
	head2.Next.Next.Next = head1.Next // 8 -> head1(2)
	fmt.Println(GetIntersectNode(head1, head2))

	// 0->9->8->6->4->5->6..
	head2 = &Node{Val: 0}
	head2.Next = &Node{Val: 9}
	head2.Next.Next = &Node{Val: 8}
	head2.Next.Next.Next = head1.Next.Next.Next.Next.Next // 8 -> head1(6)
	fmt.Println(GetIntersectNode(head1, head2))

}
```

输出：

```shell
&{6 0xc000010290}
&{2 0xc000010300}
&{4 0xc000010320}

Process finished with the exit code 0
```