前言
因为想干纯后端，所以开始刷力扣巩固算法与数据结构，结果在写几天前的每日一题的时候发现自己对于链表的操作已经有些遗忘，以及对于链表的实现等也开始忘记。于是重新复习链表，并且写下这篇文章。
本文的主要内容为：链表的理论知识、代码实现与力扣部分链表相关题目及题解。（其实本来想写全部题目的，但是共有五十多道，一是写出来篇幅太长，而是要写完这五十多道，这篇文章就不知道要拖到多久之后才能完成了）
首先给出链表的定义：链表是数据元素的线性集合。它对对象实例的每一个元素用一个单元或节点描述。节点不鄙视数组成员，节点之间的地址也不是连续的。它们的位置是通过每一个节点中明确包含了一个节点地址信息的指针来确定的。
内容
基础知识
定义
单链表就是单向链表。每一个节点中有两个域。一个是链域负责储存指向下一链表地址的指针，一个是数据域，储存数据。
类型定义：
type chainNode struct {
value int
next *chainNode
}
头节点与头指针
我们定义了链表节点后，便可以实现一个单链表了。不过为了索引单链表，我们一般会提出一个东西：头节点。
链表第一个节点不一定是头节点，但是头节点一定是链表第一个节点。头节点代表的是放在链表第一个元素（存有数据）前的节点。它的值域一般是忽略的，它的存在意义是为了方便对链表的一些操作，并不是必须定义的。
而头指针则是指向链表第一个节点的指针，如果链表存在头节点，则指向头节点，若不存在头节点，就是指向链表第一个节点。
一般情况下头节点可以不存在，但头指针必须存在，因为我们需要依靠它来找到链表。
下面我们实现一个存在头节点的链表：
type chainNode struct {
value int
next *chainNode
}
func main(){
chain := new(chainNode)
node1 := &chainNode{5,nil}
chain.next =node1
}
因为new关键字的作用是接受类型作为参数然后返回指向该类型的地址，所以这里chain便是头指针，它指向的chainNode便是头节点，二之后的node1才是真正的链表第一个元素。
单链表操作
声明：以下对节点的排序，我们默认头节点后的第一个节点为1.
链表的创建
无论是对链表进行什么操作，首先我们要创建一个链表，有了链表后才能进行操作。
而创建链表一般有两种方法，分别是头插法和尾插法
尾插法
尾插法，就是生成的每一个新节点都插入到当前链表的尾部。即将最后一个节点的链域指向它。
代码：
func createListTail(head *chainNode,n int) *chainNode{
for node := head ; node != nil ; node = node.next {
if node.next == nil {
node.next = &chainNode{n,nil}
break
}
}
return head
}
这是我们只知道头指针的情况下的尾插法，当然如果我们知道尾指针的话，就可以快速很多了，所以一般情况下会设立尾指针来方便进行尾插法。
头插法
生成的每一个节点不再是插入到链表尾部，而是插入到头节点（我们默认存在头节点）之后。
这时的操作就是新节点的链域指向头节点的下一个节点，之后头节点的链域指向新节点。
代码：
func createListHead(head *chainNode,n int) *chainNode{
node := &chainNode{n,head.next}
head.next = node
return head
}
因为不需要寻找尾指针，所以看上去更简单些
查找
其实写这个的时候挺纠结的，因为会发现各种资料中的查找有两个意思。
一个是知道序列取值，一个是知道值取地址（序列）。
不过它们的思路都是一样的，从头节点开始遍历，找出目标节点。
我以寻找第某个节点的值为例。
代码：
func get(head *chainNode,n int) (int,error) {
i := 0
for node := head ; node != nil ; node = node.next{
if i==n {
return node.value,nil
}
i++
}
return 0,errors.New("Can't Find")
}
在此基础上遍历表的所有元素，那么只需要将条件去除，每一个值都输出就可以了。
插入
若需要将某个节点插入到链表的第i位，那我们只需要将其的链域指向本来的第i位节点，然后将第i-1位的链域指向它即可。
代码：
func insert(head *chainNode,elem int,add int) (*chainNode,error) {
i := 0
for node:= head ; node != nil ; node = node.next {
if i == add-1 {
newNode := &chainNode{elem,node.next}
node.next = newNode
return head,nil
}
i++
}
return head,errors.New("overflow")
}
删除
若我们要删除第i个节点，只需将第i-1节点的链域指向第i+1，就可将第i节点从链表中删除。如果是c语言中我们还需要手动将被删除的节点的内存释放，不过考虑到go的内存释放机制，我们应该可以忽略这一步。
代码：
func del(head *chainNode,n int) {
i:=0
for node:=head;node != nil ; node = node.next {
if i == n-1 {
node.next = node.next.next
return
}
i++
}
}
力扣题型
基础题
我对基础题的定义是只需要用到上面提到的基础操作，而不需要进行额外行为。
231290.二进制链表转正数 难度：简单
链表从头到位代表一个二进制整数，现在要求将其转为十进制并返回。
比较简单，从头开始取，每拿到一个就x2+后面的。
func getDecimalValue(head *ListNode) int {
num := 0
for node := head ; node != nil ; node=node.Next {
num = num*2 +node.Val
}
return num
}
结果： 0ms 内存：2mb
剑指offer 22 链表中倒数第K个节点 难度：简单
题目的意思就是给一个数，比如3。则将从倒数第三个节点开始的链表返回。
那返回倒数第三个链表的指针不就好了。
那我们先写个简单的。首先遍历出链表长度n，那么倒数第k个节点就是正数第n-k+1的节点
func getKthFromEnd(head *ListNode, k int) *ListNode {
n:=0
cur := head
for head.Next != nil {
head = head.Next
n++
}
for i:=1;i<=n-k+1;i++ {
cur = cur.Next
}
return cur
}
结果： 4ms 内存：2.2mb
这一题还有一个有趣的解法，运行时间0ms，内存消耗只比上一种解法高几k，即是双指针。
双指针的解法想法就是，我们使用两个指针，快指针fast先走k步，然后两个指针一同运动。当fast走到尾的时候，slow正好走到了倒数第k个。
代码：
func getKthFromEnd(head *ListNode, k int) *ListNode {
slow, fast := head, head
for ;k > 0; k -- {
fast = fast.Next
}
for fast != nil {
slow, fast = slow.Next, fast.Next
}
return slow
}
876.链表的中间节点 难度：简单
题目要求简单，给出一个链表，需要返回中间节点。如果有两个中间节点就返回第二个.算是上一题的小变化
这种题目的第一个反应双指针
快指针一次走两步，慢指针一步，这样快指针走到底的时候慢指针走一半。
代码
func middleNode(head *ListNode) *ListNode {
fast := head
low := head
for fast.Next != nil && fast.Next.Next != nil {
fast=fast.Next.Next
low = low.Next
}
if fast.Next != nil {
return low.Next
}else {
return low
}
}
21.合并两个有序链表 难度：简单
思路比较简单，生成一个假头后与两个链表中的值比较，谁小就连谁，之后与该链表下一个值及另一链表当前值比较。
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
dummy := &ListNode{0,nil}
node := dummy
for l1 !=nil && l2!=nil {
if l1.Val < l2.Val {
node.Next = l1
node = node.Next
l1 = l1.Next
}else {
node.Next = l2
node = node.Next
l2 = l2.Next
}
}
switch {
case l1 != nil:
node.Next = l1
case l2 != nil:
node.Next = l2
}
return dummy.Next
}
时间复杂度：O(n^2) 内存消耗：2.5mb
双100%
进阶题
这类题型的定义是除了上述基础操作外，需要进行一些对链表链域变动的行为。
7.删除链表中的节点 难度：简单
这一题比较简单，它的要求就是只传入一个节点，然后我们要删除这个节点。
这个就比较简单了，我们只需要这个节点成为下一个节点就好了。
func deleteNode(node *ListNode) {
*node = *node.Next
}
这里有个点，就是我们写的是*node 而不是 node
因为我们这里并没有return，直接写node的话作用域只是函数内，因此需要写*node来对真实的指针进行更改。
82.删除链表中的排序元素 难度：中等
题目比较简单，因为是排序链表，一次遍历，将node与node.next对比就好了。
不过力扣不讲武德，头节点的值居然是需要考虑的有效值
所以要考虑头节点情况，就新加个节点当头节点。
然后一个指针cur开始循环，它是安全的，它要比的是next与next.next的值，如果相等就删除。
同时为了比较方便（直接比较跳过容易把奇数次重复给留个尾巴），我们写一个标志位储存val，用来对比。
代码：
func deleteDuplicates(head *ListNode) *ListNode {
newHead := &ListNode{0,head}
cur := newHead
for cur.Next != nil && cur.Next.Next != nil {
if cur.Next.Val == cur.Next.Next.Val{
v := cur.Next.Val
for cur.Next != nil && cur.Next.Val == v {
cur.Next = cur.Next.Next
}
}else {
cur = cur.Next
}
}
return newHead.Next
}
19.删除链表的倒数第N个节点 难度：中等
这就是倒数第k个节点与删除节点的组合
快慢指针解决
func removeNthFromEnd(head *ListNode, n int) *ListNode {
dummpy := &ListNode{0,head}
fast,slow := dummpy,dummpy
for n>=0 {
fast = fast.Next
n--
}
for fast != nil {
slow,fast = slow.Next,fast.Next
}
if slow.Next.Next!=nil{
slow.Next = slow.Next.Next
}else{
slow.Next = nil
}
return dummpy.Next
}
206.反转链表 && 剑指Offer 24 难度：简单
加上头指针一共用了三个指针的遍历法
一个pre，记录.next 一个cur记录上一节点。
如图，这是一开始的样子
然后，将head.next指向cur，cur=head，head=pre，pre=head.next
就变成了这样，由此往复，便可将链表完全倒转过来
代码：
func reverseList(head *ListNode) *ListNode {
var cur *ListNode
for head != nil {
pre := head.Next
head.Next = cur
cur = head
head = pre
}
return cur
}
面试题02.07 链表相交 难度：简单
检查两个链表中是否有节点相交
一开始想的是遍历来对比，后来发现还是可以双指针解法
如果两个链表相交的话，那么当两个指针在走完自己链表后走对面链表的话，必定会相交。
a
o - c
b /
这样看，假设两指针分别从a、b到c，之后再从b、a到c
那么它们的移动距离分别是 ao+ob+bo=bo+oc+ao，再加上两指针速度相同，所以他们必定相遇
那么当他们相遇，且有值当时候，就说明两链表相交
func getIntersectionNode(headA, headB *ListNode) *ListNode {
p1, p2 := headA, headB
for p1 != p2 {
if p1 == nil {
p1 = headB
} else {
p1 = p1.Next
}
if p2 == nil {
p2 = headA
} else {
p2 = p2.Next
}
}
return p1
}
234.回文链表 难度：简单
快慢指针找重点断开后做链表反转然后对比
func isPalindrome(head *ListNode) bool {
if head == nil || head.Next == nil{
return true
}
slow,fast := head,head
var pre *ListNode
for fast!=nil && fast.Next != nil {
pre = slow
slow = slow.Next
fast = fast.Next.Next
}
pre.Next = nil
var dummy *ListNode
for slow != nil {
fast = slow.Next
slow.Next = dummy
dummy = slow
slow = fast
}
for dummy!=nil && head != nil {
if dummy.Val != head.Val{
return false
}
head = head.Next
dummy = dummy.Next
}
return true
}
剑指offer 35.复杂链表的复制 难度：中等
这一题的解法可以这样。
我们先将之当成单链表，复制节点的next与val，然后再复制指针。
但是直接复制指针的话，指向地址不是新节点的地址。 我们可以将新节点直接插入每一个旧节点之后，然后指针=旧指针指向节点的next
之后我们再将新节点都分离出来，新成新链表输出。(记得将原链表拼回去，不然会报错Next pointer of node with label 13 from the original list was modified.)
代码：
func copyRandomList(head *Node) *Node {
if head == nil {
return nil
}
node := head
for node!=nil {
newNode := &Node{
node.Val,
node.Next,
nil,
}
node.Next = newNode
node = newNode.Next
}
node = head
for node!=nil {
if node.Random != nil {
node.Next.Random = node.Random.Next
}
node = node.Next.Next
}
newHead := head.Next
oldNode := head
node = newHead
for node.Next != nil {
oldNode.Next = oldNode.Next.Next
node.Next = node.Next.Next
oldNode = oldNode.Next
node = node.Next
}
oldNode.Next = nil
return newHead
}
142.环形链表2 难度：中等
快慢指针解法。不过需要注意一个问题，那就是我们快慢指针会相遇，但不一定会在第一个节点相遇。
func detectCycle(head *ListNode) *ListNode {
slow,fast := head,head
for fast != nil&&fast.Next != nil { //考虑有指向nil这种阴间行为，记得.next!=nil
slow = slow.Next
fast = fast.Next.Next
if slow == fast{
node := head
for node != slow {
node = node.Next
slow = slow.Next
}
return node
}
}
return nil
148.排序链表 难度：中等
想法1 直接取值入数组排序然后重写
func sortList(head *ListNode) *ListNode {
l1 := []int{}
for node:=head;node != nil ;node = node.Next{
l1 = append(l1,node.Val)
}
sort.Ints(l1)
i:=0
for node:=head;node !=nil;node=node.Next{
node.Val = l1[i]
i++
}
return head
}
我本来以为超时的，没想到通过了
常规解法是归并排序
我们先将链表多次等分，得出单个链表。
然后结合之前的合并有序链表的想法进行两两合并，得出结果
func sortList(head *ListNode) *ListNode {
if head == nil || head.Next == nil { // 递归的出口，不用排序 直接返回
return head
}
slow,fast := head,head
var pre *ListNode
for fast != nil && fast.Next != nil {
pre = slow
slow = slow.Next
fast = fast.Next.Next
}
pre.Next = nil
l1 := sortList(head)
l2 := sortList(slow)
return mergeList(l1,l2)
}
func mergeList(l1,l2 *ListNode) *ListNode {
dummy := &ListNode{0,nil}
node := dummy
for l1!=nil && l2!=nil {
if l1.Val < l2.Val {
node.Next = l1
l1 = l1.Next
}else {
node.Next = l2
l2 = l2.Next
}
node = node.Next
}
switch {
case l1 != nil:
node.Next = l1
case l2 != nil:
node.Next = l2
}
return dummy.Next
}
23.合并K个升序链表 难度：困难
最后以一个困难结尾，听说这个题也是字节面试喜欢问的 合并链表的升级版，简单解法就是不断循环
func mergeKLists(lists []*ListNode) *ListNode {
if len(lists) == 0 {
return nil
}
end := lists[0]
for i:=1;i<len(lists);i++{
end = merge(end,lists[i])
}
return end
}
func merge(l1,l2 *ListNode) *ListNode {
dummy := &ListNode{0,nil}
node := dummy
for l1!=nil && l2!=nil {
if l1.Val < l2.Val {
node.Next = l1
l1 = l1.Next
}else {
node.Next = l2
l2 = l2.Next
}
node = node.Next
}
switch {
case l1 != nil:
node.Next = l1
case l2 != nil:
node.Next = l2
}
return dummy.Next
}
时间复杂度： O(k^2*n)
那么有没有优美解法呢
有一个最小堆法和一个分治法，实话实说最小堆法我没看出优化的地方，所以我先写分治法
分治法的思路比较简单，归并排序，我们先将链表数组无限细分至每组只有两个链表，然后链表合并后与其他链表合并直到最后结果
func mergeKLists(lists []*ListNode) *ListNode {
if len(lists) == 0 || lists == nil {
return nil
}
return mergeControl(lists,0,len(lists)-1)
}
func mergeControl(lists []*ListNode,start,end int) *ListNode{
if start == end { // 仅剩一个链表，返回上一步与隔壁链表进行合并
return lists[start]
}
if start>end {
return nil
}
mid := (start+end)/2
l1 := mergeControl(lists,start,mid)
l2 := mergeControl(lists,mid+1,end)
return merge(l1,l2)
}
func merge(l1,l2 *ListNode) *ListNode {
dummy := &ListNode{0,nil}
node := dummy
for l1!=nil && l2!=nil {
if l1.Val < l2.Val {
node.Next = l1
l1 = l1.Next
}else {
node.Next = l2
l2 = l2.Next
}
node = node.Next
}
switch {
case l1 != nil:
node.Next = l1
case l2 != nil:
node.Next = l2
}
return dummy.Next
}