【269期】链表高频面试题（包括反转、合并、相交、分割、环长等）

1.整个链表翻转

https://leetcode-cn.com/problems/reverse-linked-list/

1.1 题目描述

反转一个单链表。

示例:

• 输入: 1->2->3->4->5->NULL
• 输出: 5->4->3->2->1->NULL

进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

1.2 算法实现

1.2.1 算法思路

双指针：一个指针pre指向原链表当前节点的前一个节点，另一个指针next暂存当前节点的下一个节点。

依次遍历链表的各个节点，每遍历一个节点即将其指向前一个节点（倒置），主要分4步：

1. 先备份后一个节点（以防移动指针的时候找不到下一个节点）：next = head.Next；
2. 后一个节点的Next指向前一个节点：next.Next = pre；
3. 前置节点后移一个位置到当前节点：pre = head;
4. 后置节点后移一个位置到下一个节点：head = next，注意这一步（千万不要）容易忽略。

1.2.2 代码实现

type LikedList struct{
    Val int
    Next *LikedList
}

// 头插法，倒置单链表
func reverseLikedList(head *LikedList)*LikedList{
    if(head == nil || head.Next == nil){
        return head
    }
 var pre, next *LikedList 
 // head是当前节点，pre是当前节点的前一个几点，next是当前节点的后一个节点
    for head != nil {  // 当前节点不为空
        next = head.Next    // 备份head.Next（指向当前节点的下一个节点），防止移动节点时找不到后置节点
  head.Next = pre     // 更新head.Next，后一个节点指向前一个（翻转）
  pre = head          // 前一个节点后移
  head = next   // 当前节点后移
 }
    return pre              // 注意：当pre指向原链表的最后一个节点时，head已经指向最后一个节点的Next即空节点，所以这里应返回pre
}

2.反转链表中的第m至第n个节点

题目来源：

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

2.1 题目描述

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:

1 ≤ m ≤ n ≤ 链表长度。

示例:

• 输入: 1->2->3->4->5->NULL, m = 2, n = 4
• 输出: 1->4->3->2->5->NULL

2.2 算法实现

2.2.1 算法思路

有四个关键的位置需要记录：第m个节点及其前驱节点、第n个节点及其后继节点。

1. 对整个链表遍历，将链表head的头指针向后移动m-1个节点，即为第m个节点，记其前驱节点为pre；
2. 自第m个节点开始逆置changLen = n-m+1个节点，即将第m至第n个节点依次反转，并记录下来反转后的头结点reversedListHead和尾节点reversedListTail；
3. 将反转后的尾节点reversedListTail的Next域与第n个节点的后继节点head连接，pre节点的Next域与reversedListHead连接。

2.2.2 代码实现

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseBetween(head *ListNode, m int, n int) *ListNode {
    changeLen := n - m + 1                      // 计算需要逆置的节点个数
    var pre *ListNode = nil                     // 初始化开始逆置的节点的前驱
    var result *ListNode = head                 // 最终转换后的链表的头结点，非特殊情况即为head
    move := m - 1                               // head向后移动m-1个位置指向第m个节点
    for(head != nil && move > 0){               // 将head后移m-1个位置，即
        pre = head                              // for循环后pre指向第m个节点的前驱节点
        head = head.Next                        // for循环后head指向第m个节点
        move--
    }

    var reversedListTail *ListNode = head       // 此时reversedListTail指向的是第m个节点，该节点即是链表片段反转后的尾节点
    var reversedListHead *ListNode = nil        // 记录链表片段反转后的头结点
    for(head != nil && changeLen > 0){          // 逆置changeLen个节点
        next := head.Next                       // 暂存当前节点的下一个节点
        head.Next = reversedListHead            // 当前节点的Next指针域指向新开辟的反转后的头结点
        reversedListHead = head                 // 反转后的链表的头结点后移一个位置
        head = next                             // 当前节点后移一个节点
        changeLen--                             // 每完成一个节点逆置，changLen--
    }

    reversedListTail.Next = head                // 连接逆置后的链表尾与逆置段的后一个节点，翻转后的尾节点指向第n个节点的下一个节点
    if(pre != nil){                             // 如果pre不为空，说明不是从第1个节点开始逆置的，即m > 1 
        pre.Next = reversedListHead             // 将逆置链表开始的节点前驱与逆置后的头结点连接起来
    }else{                                      // 如果pre为空，说明m=1，即从第1个节点开始逆置，结果即为逆置后的头结点
        result = reversedListHead
    }
    return result
}

3.求两个链表之间的交点

3.1 题目描述

题目来源：

https://leetcode-cn.com/problems/intersection-of-two-linked-lists

编写一个程序，找到两个单链表相交的起始节点。

如下面的两个链表：

在节点 c1 开始相交。

示例 1：

• 输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
• 输出：Reference of the node with value = 8

输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

推荐：250期面试题汇总

示例 2：

• 输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
• 输出：Reference of the node with value = 2

输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

• 输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
• 输出：null

输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。解释：这两个链表不相交，因此返回 null。

注意：

• 如果两个链表没有交点，返回 null.
• 在返回结果后，两个链表仍须保持原有的结构。
• 可假定整个链表结构中没有循环。
• 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

3.2 算法实现

3.2.1 算法思路

1. 对两个链表ListNode1和ListNode2分别遍历，计算出其长度len1和len2；
2. 长链表的头指针后移abs(len1 - len2)个节点；
3. 当链表未遍历到头，两链表指向同一个节点时，该节点即为两链表的交点，没有指向同一个节点则两个头结点指针继续后移；遍历完还没有找到，则说明没有交点，返回nil。

3.2.2 代码实现

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    var lenA, lenB int                                      // 分别记录链表headA和链表headB的长度    
    lenA = getListLength(headA)
    lenB = getListLength(headB)

    if lenA > lenB {
        headA = forwardDeltaLenNode(lenA, lenB, headA)      // headA链表的头结点指向移动多出的节点个位置后
    }else{
        headB = forwardDeltaLenNode(lenB, lenA, headB)      // 如果链表headB长，移动其头结点到相应位置
    }
    for headA != nil && headB != nil {      // 没有到达链表末尾
        if(headA == headB){                 // 当前两个链表的节点相同，即指向同一个节点，说明找到的交点；否则，两链表同时后移
            return headA
        }
        headA = headA.Next                  
        headB = headB.Next
    }
    return nil                              // 遍历到链表末尾还没有找到同一个节点，说明两链表没有交点
}

// 逐个节点遍历，获取链表长度
func getListLength(head *ListNode)int{
    var lengthList int 
    for head != nil {
        lengthList++
        head = head.Next
    }
    return lengthList
}

// 较长链表移动 长链表长度-短链表长度 个节点后对应的头指针
// 参数longLen和shortLen分别表示长链表和短链表的长度，longList对应长链表
func forwardDeltaLenNode(longLen, shortLen int, longList *ListNode)*ListNode{
    deltaLen := longLen - shortLen
    for longList != nil && deltaLen != 0{
        longList = longList.Next
        deltaLen--
    }
    return longList             // 如果longList为nil或者deltaLen=0直接返回此时的头结点longList
}

4.判断链表是否有环；如果有环，给出环所在的起始节点及环的长度。

4.1 判断链表是否有环

4.2 给出有环链表的环的起始节点及长度

5.将链表换分为以某个值x为界限的前后两部分

链表划分依据：链表前面的部门小于x，后面部分大于等于x，且原有节点的相对顺序不变。如：将1->3-7->2->5->3->6-9-2划分为以5为界限的前后两部分：1->3->2->3->2 ->7->5->6->9

5.1 问题描述

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

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

示例:

• 输入: head = 1->4->3->2->5->2, x = 3
• 输出: 1->2->2->4->3->5

链接：

https://leetcode-cn.com/problems/partition-list

5.2 算法实现

5.2.1 算法思路

链表分为前后两个部分，可以先依次遍历链表，将小于x的节点依次插入到preHead指向的前半部分链表后面，将大于等于x的节点连接到postHead对应的另一个链表中；链表遍历完将preHead的尾节点的Next域指向postHead结点的下一个节点，postHead的尾节点的Next域置为空，即实现了前后两个链表的连接。

为了连接preHead和postHead两个链表，需要分别知道两个链表的尾部，这里使用prePtr和postPtr指针分别对preHead和postHead进行遍历，知道两个链表的尾节点。

• 前一个链表：preHead->1->2->2
• 后一个链表：postHead->4->3->5

5.2.2 代码实现

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func partition(head *ListNode, x int) *ListNode {
    //var preHead, postHead *ListNode     // 前后两部分链表的头结点，不能这么声明，这样声明的话两者都为&ListNode{0, nil}其中Next域为nil，当运行到prePtr.Next = head时会报panic: runtime error:invalid memory address or nil pointer deference错误
    preHead := &ListNode{0, nil}        // 生成一个preHead链表的头结点，该节点固定一直不对其移动，改头节点的Val为多少都不影响结果，因为使用的是头结点的Next节点
    postHead := &ListNode{0, nil}       // 生成一个postHead链表的头结点，该节点固定不动
    prePtr := preHead                   // prePtr指针对preHead链表进行遍历，注意：开始时其指向preHead
    postPtr := postHead
    for head != nil {                   // 遍历原链表
        if(head.Val < x ){              // 小于x的节点尾插到preHead链表后面
            prePtr.Next = head          // prePtr的Next域指向当前节点，即将当前节点从preHead链表尾部prePtr依次插入
            prePtr = head               // prePtr指针后移一位，指向当前节点
        }else{                          // 大于等于x的节点放在postHead链表的后面
            postPtr.Next = head         // 将当前节点插入到postHead链表尾节点postPtr后面
            postPtr = head              // postHead链表的尾节点后移一位
        }
        head = head.Next                // 当前指针后移一位
    }
    // 对head链表遍历结束分为preHead和postHead两个子链表
    prePtr.Next = postHead.Next         // 注意：这里是将preHead链表的尾节点prePtr的Next域指向postHead链表头结点的下一个节点
    postPtr.Next = nil                  // postPtr的尾节点的Next域指向空
    return preHead.Next                 // 返回preHead链表的Next之后的链表
}