查看原文
其他

【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之后的链表
}


来源:gonline.blog.csdn.net/article/details/104187852

END

十期推荐

【251期】面试官:谈谈你对零拷贝的理解~
【252期】运行时常量池的一道面试题(JDK8环境)
【253期】面试官:熟悉Docker操作吗?说几个常用的Docker命令吧
【254期】面试官:来谈谈微服务组件Feign的工作原理吧
【255期】面试官:Mybatis是如何运用设计模式的?
【256期】面试官常考的 21 条 Linux 命令
【257期】面试官:谈谈你对Java线程安全与不安全的理解
【258期】今日头条的面试题:LRU原理和Redis实现
【259期】面试官:Spring事务失效的场景有哪些?如何解决?
【260期】Java线程池,这篇能让你和面试官聊了半小时


与其在网上拼命找题? 不如马上关注我们~

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存