专题3：链表类题型总结（go）

1、总结

链表类问题都是in-place，空间复杂度都是O(1)的，在所有的排序算法中，时间复杂度为O(nlogn)的有三个：

1）快速排序（不开辟空间）；

2）归并排序（需要开辟O(n)的空间，但是在list问题上不开辟空间）；

3）堆排序（首先需要有一个堆）。

 while里面写判断条件的时候规律：

如果接下来有head -> next，那么必须判断head是否为空，同理类推。

写链表的题目，一定要注意是否需要返回node，有些题目是void就是没有返回值的，自己经常没注意这个void就直接返回值了。

1.1、Remove Duplicates from Sorted List

https://leetcode.com/problems/remove-duplicates-from-sorted-list/#/description

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次 。

返回同样按升序排列的结果链表。

思路：使用一个node，相等的时候就node -> next = node -> next -> next，不相等的时候node往后移位.

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func deleteDuplicates(head *ListNode) *ListNode {
    if head == nil {
        return head
    }

    dummy := head
    for dummy.Next != nil {
        if dummy.Val == dummy.Next.Val {
            dummy.Next = dummy.Next.Next
        } else {
            dummy = dummy.Next
        } 
    }
    
    return head
}

1.2、Remove Duplicates from Sorted List II

https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/#/description

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现 的数字。

返回同样按升序排列的结果链表。

dummy node标准写法：

哨兵节点使用于头结点不确定的情况，题目中可能需要单独对头结点进行操作，这时候就可以引入哨兵节点。

dummy := &ListNode{

　　0,

　　head,

}

head = dummy

...

return dummy.next;

3）因为本题需要知道前驱节点，这样才能将所有重复的节点去掉，所以需要使用head->next和head->next->next。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func deleteDuplicates(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }

    dummy := &ListNode{
        0,
        head,
    }
    head = dummy

    for head.Next != nil && head.Next.Next != nil {
        if head.Next.Val == head.Next.Next.Val {
            flag := head.Next.Val
            for head.Next != nil && head.Next.Val == flag{
                head.Next = head.Next.Next
            }
        } else {
            head = head.Next
        }
    }

    return dummy.Next
}

1.3  Reverse Linked List

反转一个单链表。

思路：记得保存断开后的下一个节点。

https://leetcode.com/problems/reverse-linked-list/#/description

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }

    var pre, cur, post *ListNode = nil, head, head.Next
    for cur != nil {
        post = cur.Next
        cur.Next = pre
        pre = cur
        cur = post 
    }
    return pre
}

1.4 Reverse Linked List II

https://leetcode.com/problems/reverse-linked-list-ii/#/description

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

思路：这题需要考虑m和n的关系，m为1的时候，是头结点，这时候很难处理，就需要引入dummy node，技巧点：因为多了一个节点，所以i=1，循环m-1次，找到m的前一个位置，循环里面判断是否为空的判断是为了判断m是否大于链表的长度。
接下来令nNode = mNode，循环n-m次，j =m.j < n。交换相邻节点，记得判断postnNode是否为空，为空则返回，而且也记得上面的总结，后面有postnNode -> next，所以要判断postnNode是否为空，为空则n大于链表长度，返回NULL。

func reverseBetween(head *ListNode, left, right int) *ListNode {

 　　  if head == nil || left >= right{

          return head

    　 }

// 设置 dummyNode 是这一类问题的一般做法
    dummyNode := &ListNode{Val: -1}
    dummyNode.Next = head
    pre := dummyNode
    for i := 0; i < left-1; i++ {
        pre = pre.Next
    }
    cur := pre.Next
    for i := 0; i < right-left; i++ {
        next := cur.Next
        cur.Next = next.Next
        next.Next = pre.Next
        pre.Next = next
    }
    return dummyNode.Next
}

反转链表递归和迭代版本

原题：leetcode 206. Reverse Linked List 

           Reverse a singly linked list.

迭代版本：

　　思路：通过举例分析可以知道，在反转其中一个链表后，会发生断裂情况，没法知道下一个链节点，需要建立三个节点，所以需要首先保存后一个节点，然后将后一个结点的next指向前一个节点，接下来依次后退，pPre=pCur;pCur=pNext。

　递归版本：思路和迭代差不多，只不过在最后两个节点交换的时候，使用递归版本实现。递归要考虑到原函数初始定义会在后面递归的时候不断的重新定义，这里思考出现卡顿，所以引入一个辅助函数。

1.5 Partition List

https://leetcode.com/problems/partition-list/#/description

将比x小的元素放在前面，小的元素放在后面。

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你应当 保留 两个分区中每个节点的初始相对位置。

思路：使用两个dummy node,分别记录比x大的数和比x小的数，最后将两者合并起来。链表的结尾必须要加上nullptr，这题dummyRight最后要dummyNode -> next = nullptr.

https://leetcode-cn.com/problems/partition-list/solution/fen-ge-lian-biao-by-leetcode-solution-7ade/

func partition(head *ListNode, x int) *ListNode {
    small := &ListNode{}
    smallHead := small
    large := &ListNode{}
    largeHead := large
    for head != nil {
        if head.Val < x {
            small.Next = head
            small = small.Next
        } else {
            large.Next = head
            large = large.Next
        }
        head = head.Next
    }
    large.Next = nil
    small.Next = largeHead.Next
    return smallHead.Next
}

1.6 Sort List

https://leetcode.com/problems/sort-list/#/description

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

进阶：

你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

思路：记住归并算法在list结构中 ，所需要的空间复杂度是O(1)的，注意该题边界条件有两个变量需要考虑，不能漏写。

if(head == NULL || head -> next == NULL){//边界情况
      return head;
}

这题就使用归并算法。三步走：

1）找中间函数使用快慢指针找到链表的中间，slow = head ，fast = head -> next。快指针走两步，慢指针走一步，当fast为空的时候，就找到了slow = mid；

2）使用递归函数将问题分解，

ListNode* mergeRight = sortList(mid -> next);
mid -> next = NULL;
ListNode*  mergeLeft = sortList(head);

这里有个细节，就是要将mid-> next设为空，不然就会陷入死循环。先传给右边，也可以省掉一个节点。

3）新建dummy node和tail node，哪个大就将该节点赋到tail后面，最后返回dummy -> next。

https://leetcode-cn.com/problems/sort-list/solution/pai-xu-lian-biao-by-leetcode-solution/

func merge(head1, head2 *ListNode) *ListNode {
    dummyHead := &ListNode{}
    temp, temp1, temp2 := dummyHead, head1, head2
    for temp1 != nil && temp2 != nil {
        if temp1.Val <= temp2.Val {
            temp.Next = temp1
            temp1 = temp1.Next
        } else {
            temp.Next = temp2
            temp2 = temp2.Next
        }
        temp = temp.Next
    }
    if temp1 != nil {
        temp.Next = temp1
    } else if temp2 != nil {
        temp.Next = temp2
    }
    return dummyHead.Next
}

func sort(head, tail *ListNode) *ListNode {
    if head == nil {
        return head
    }

    if head.Next == tail {
        head.Next = nil
        return head
    }

    slow, fast := head, head
    for fast != tail {
        slow = slow.Next
        fast = fast.Next
        if fast != tail {
            fast = fast.Next
        }
    }

    mid := slow
    return merge(sort(head, mid), sort(mid, tail))
}

func sortList(head *ListNode) *ListNode {
    return sort(head, nil)
}

 1.7 Reorder List

https://leetcode.com/problems/reorder-list/#/description

思路：首先找中点，使用快慢指针；然后将右边的元素全部反转，参考reverse函数；最后将两个链表合并。注意点mid这个node属于left链表。　

给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

　

寻找链表中点 + 链表逆序 + 合并链表
注意到目标链表即为将原链表的左半端和反转后的右半端合并后的结果。

这样我们的任务即可划分为三步：

找到原链表的中点（参考「876. 链表的中间结点」）。

我们可以使用快慢指针来 O(N)O(N) 地找到链表的中间节点。
将原链表的右半端反转（参考「206. 反转链表」）。

我们可以使用迭代法实现链表的反转。
将原链表的两端合并。

因为两链表长度相差不超过 1，因此直接合并即可。

func middleNode(head *ListNode) *ListNode {
    slow, fast := head, head
    for fast.Next != nil && fast.Next.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    return slow
}

func reverseList(head *ListNode) *ListNode {
    var prev, cur *ListNode = nil, head
    for cur != nil {
        nextTmp := cur.Next
        cur.Next = prev
        prev = cur
        cur = nextTmp
    }
    return prev
}

func mergeList(l1, l2 *ListNode) {
    var l1Tmp, l2Tmp *ListNode
    for l1 != nil && l2 != nil {
        l1Tmp = l1.Next
        l2Tmp = l2.Next

        l1.Next = l2
        l1 = l1Tmp

        l2.Next = l1
        l2 = l2Tmp
    }
}

func reorderList(head *ListNode) {
    if head == nil {
        return
    }
    mid := middleNode(head)
    l1 := head
    l2 := mid.Next
    mid.Next = nil
    l2 = reverseList(l2)
    mergeList(l1, l2)
}

2 Fast Slow Pointers

2.1 有环链表问题总结

1）Linked List Cycle I

https://leetcode.com/problems/linked-list-cycle/#/description

给定一个链表，判断链表中是否有环。

思路：快慢指针，相交的话则有环

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func hasCycle(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return false
    }

    slow, fast := head, head.Next
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            return true
        } 
    }

    return false
}

2）Linked List Cycle II

https://leetcode.com/problems/linked-list-cycle-ii/#/description

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

思路:这题需要知道a = c，然后head和slow每次走一步，相遇的时候就是第一个入口交点，需要注意应该写head != slow -> next,如果写成head == slow，在两个元素组成的环中就会死循环

还有就是最后返回head， return head;//这里不能写成slow，因为两个元素的环就出错。

func detectCycle(head *ListNode) *ListNode {
    slow, fast := head, head
    for fast != nil {
        slow = slow.Next
        if fast.Next == nil {
            return nil
        }
        fast = fast.Next.Next
        if fast == slow {
            p := head
            for p != slow {
                p = p.Next
                slow = slow.Next
            }
            return p
        }
    }
    return nil
}

 参考答案：https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/huan-xing-lian-biao-ii-by-leetcode-solution/

在网上搜集了一下这个问题相关的一些问题，总结如下：

1. 环的长度是多少？

2. 如何找到环中第一个节点（即Linked List Cycle II）？

3. 如何将有环的链表变成单链表（解除环）？

4. 如何判断两个单链表是否有交点？如何找到第一个相交的节点？

首先我们看下面这张图：

设：链表头是X，环的第一个节点是Y，slow和fast第一次的交点是Z。各段的长度分别是a,b,c，如图所示。环的长度是L。slow和fast的速度分别是qs,qf。

下面我们来挨个问题分析。

1. 方法一（网上都是这个答案）：

第一次相遇后，让slow,fast继续走，记录到下次相遇时循环了几次。因为当fast第二次到达Z点时，fast走了一圈，slow走了半圈，而当fast第三次到达Z点时，fast走了两圈，slow走了一圈，正好还在Z点相遇。

方法二：

第一次相遇后，让fast停着不走了，slow继续走，记录到下次相遇时循环了几次。

方法三（最简单）：

第一次相遇时slow走过的距离：a+b，fast走过的距离：a+b+c+b。

因为fast的速度是slow的两倍，所以fast走的距离是slow的两倍，有 2(a+b) = a+b+c+b，可以得到a=c（这个结论很重要！）。

我们发现L=b+c=a+b，也就是说，从一开始到二者第一次相遇，循环的次数就等于环的长度。

2. 我们已经得到了结论a=c，那么让两个指针分别从X和Z开始走，每次走一步，那么正好会在Y相遇！也就是环的第一个节点。

3. 在上一个问题的最后，将c段中Y点之前的那个节点与Y的链接切断即可。

4. 如何判断两个单链表是否有交点？先判断两个链表是否有环，如果一个有环一个没环，肯定不相交；如果两个都没有环，判断两个列表的尾部是否相等；如果两个都有环，判断一个链表上的Z点是否在另一个链表上。

如何找到第一个相交的节点？求出两个链表的长度L1,L2（如果有环，则将Y点当做尾节点来算），假设L1<L2，用两个指针分别从两个链表的头部开始走，长度为L2的链表先走(L2-L1)步，然后两个一起走，直到二者相遇。

 2.2 Merge k Sorted Lists（important）参考嘻唰唰的链接

https://leetcode.com/problems/merge-k-sorted-lists/#/description

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

时间复杂度为O(NlogK)，

思路2：采用递归中的分治算法，也是二分方法，先处理相等的时候，递归基，然后再归并。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func  mergeSort(left *ListNode, right *ListNode) *ListNode {
    dummy := &ListNode{Val:0}
    tail := dummy
    for left != nil && right != nil {
        if left.Val < right.Val {
            tail.Next = left
            left = left.Next
        } else {
            tail.Next = right
            right = right.Next
        }
        tail = tail.Next
    }
    if left != nil {
        tail.Next = left
    }

    if right != nil {
        tail.Next = right
    }
    return dummy.Next
}

func merge(lists []*ListNode, start int, end int) *ListNode {
    if start == end {
        return lists[start]
    }

    var mid int
    mid = start + (end - start) / 2
    left := merge(lists, start, mid)
    right := merge(lists, mid + 1, end)
    return mergeSort(left, right)
}

func mergeKLists(lists []*ListNode) *ListNode {
    if len(lists) == 0 {
        return nil
    }

    return merge(lists, 0, len(lists) - 1)
}

迭代版本：

 

2.3 138. Copy List with Random Pointer

https://leetcode.com/problems/copy-list-with-random-pointer/#/description

思路：建立两个节点，哨兵节点最后返回结果，一个随着计算进行next，首先只要当前节点不为空，就不断将node压入一个哈希表unordered_map，这个map里面可以是原来表的node，value是新的node，接下来的循环是拷贝随机指针，Map[tmp] -> random = Map[tmp -> random];

 调整只需要O(1)空间复杂度的解法：

思路：三部曲：

1. 在原链表的每个节点后面拷贝出一个新的节点

2. 依次给新的节点的随机指针赋值，因为在第一步中，新节点和旧节点都指向相同的随机指针元素，这个赋值非常容易 cur->next->random = cur->random->next，要注意这里cur->random不能为空，初始化都为空，只有不为空的时候才需要调整。

3. 断开链表可得到深度拷贝后的新链表，这里需要注意的地方是

if(tmp->next != NULL){
//只有一个节点的时候1 -> 1' -> NULL;tmp -> next == NULL 
　　tmp -> next = tmp -> next -> next;
}

正常思路的好方法：记住要先保存head，因为后面要copy随机节点。

分析复杂度的方法：

看均到每个节点上的复杂度是多少，然后乘以N个节点，就可以得到总的时间复杂度。

 2.4 109. Convert Sorted List to Binary Search Tree

https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/#/description

排序链表转化为二叉搜索树

思路：二叉树中序递归遍历的思路，首先求出链表的长度，然后定义递归函数helper(*&head,start,end)，参考了嘻唰唰的思路----->这里这个函数所做的是将*head为头的linked list构建成一个BST，然后返回BST的root，而同时，也将head移动到linked list中第end+1个节点。因为*head既是输入参数，也是返回参数，所以这里用到了指针的引用*&head。注意不能错写成了&*head。理解*&的方法是从右向左读：首先是一个引用，然后是一个对指针的引用，最后是一个对ListNode指针的引用。

那么当left subtree构建完成后，head指向了mid，构建mid树节点。然后后移head到right subtree在linked list中的头节点。继续递归构建right subtree.

 

跑一个例子：

linked list: 0->1->2->NULL

 

                                                             call (head(0), 0, 2)

                                                                    mid = 1

                                                             node(1), head(2)

                                                /                                              

                       call (head(0), 0, 0)                                        call (head(2), 2, 2)

                               mid = 0                                                         mid = 2

                       node(0), head(1)                                           node(2), head(NULL)

                        /                                                                  /                        

call (head(0), 0, -1)            call (head(0), 1, 0)     call (head(2), 2, 1)          call (head(0), 2, 1)

return NULL                       return NULL               return NULL                    return NULL

 

最终结果：

    1

  /    

0      2

需要注意的坑是： int len = 0;//len必须初始化为0，后面才能进行自增操作，head = head -> next;//记住链表分割的时候一定要修改传递的head节点，这里的递归有点难理解，先看递归基的情况，然后回溯的构造结果，每次返回给上一层的是该层的root。

 思路2：可以直接使用全局变量，避免复杂的写法。

思路3：先找到中间点，然后找left，在找right，递归执行，每次需要使用快慢指针找到中间点。

另一道简单的数组题和这个思路差不多，108. Convert Sorted Array to Binary Search Tree

2.5 二叉搜索树与双向链表

https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5?tpId=13&tqId=11179&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

思路：题目中说要求不能创建任何新的结点，指的是不能new一个节点出来，但是可以创建局部变量。二叉树有左右两个指针，而链表也有前后两个指针，helper函数里面有两个节点，第二个pre是传引用的形式，最后的结果pre指向链表的最后一个节点，所以要得到头结点，需要不断的pre = pre -> left;

1）先将左子树构建成一个链表

2）root -> left = pre;pre -> right = root

pre = root ;

3)接下来转入右子树，将右子树转化为链表，递归执行

2.6 25. Reverse Nodes in k-Group

https://leetcode.com/problems/reverse-nodes-in-k-group/#/description

思路：这题我是联想给定一个链表，反转第m和n之间链表的解法，在画图分析的基础上，增加了一个外层循环，循环次数是k/listLen；因为要修改第一个节点，所以需要一个dummy node，

每次调整k之后，需要将prem和m节点进行调整：

prem = m;
m = postn;

还有记得循环的次数可以通过举两个节点的简单例子进行确定。