【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步:
先备份后一个节点(以防移动指针的时候找不到下一个节点):next = head.Next; 后一个节点的Next指向前一个节点:next.Next = pre; 前置节点后移一个位置到当前节点:pre = head; 后置节点后移一个位置到下一个节点: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个节点及其后继节点。
对整个链表遍历,将链表head的头指针向后移动m-1个节点,即为第m个节点,记其前驱节点为pre; 自第m个节点开始逆置changLen = n-m+1个节点,即将第m至第n个节点依次反转,并记录下来反转后的头结点reversedListHead和尾节点reversedListTail; 将反转后的尾节点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 算法思路
对两个链表ListNode1和ListNode2分别遍历,计算出其长度len1和len2; 长链表的头指针后移abs(len1 - len2)个节点; 当链表未遍历到头,两链表指向同一个节点时,该节点即为两链表的交点,没有指向同一个节点则两个头结点指针继续后移;遍历完还没有找到,则说明没有交点,返回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之后的链表
}
来源:gonline.blog.csdn.net/article/details/104187852
END
十期推荐
与其在网上拼命找题? 不如马上关注我们~