【面试必刷TOP101】删除链表的倒数第n个节点 & 两个链表的第一个公共结点

简介: 【面试必刷TOP101】删除链表的倒数第n个节点 & 两个链表的第一个公共结点

题目:删除链表的倒数第n个节点_牛客题霸_牛客网 (nowcoder.com)

题目的接口:

package main
import . "nc_tools"
/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */
/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @param n int整型 
 * @return ListNode类
*/
func removeNthFromEnd( head *ListNode ,  n int ) *ListNode {
    // write code here
}

解题思路:

这道题的解题思路其实和上一题找出倒数后 k 个节点的思路是一样的,首先就是用快慢指针把 k 的位置找到,这里需要删除这个位置的节点,那咱们只需要把它的前一个节点找到就行,

所以只需要设置一个 prev 节点作为他的上一个节点就搞定了,代码如下:

代码:

package main
import . "nc_tools"
/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */
/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @param n int整型 
 * @return ListNode类
*/
func removeNthFromEnd( head *ListNode ,  n int ) *ListNode {
    fast := head
    slow := head
    prev := head
    for i := 0; i < n; i++ {
        fast = fast.Next
    }
    for fast != nil {
        slow = slow.Next
        fast = fast.Next
    }
    if prev == slow {
        return slow.Next
    } else {
        for prev.Next != slow {
            prev = prev.Next
        }
        prev.Next = slow.Next
    }
    return head
}

过啦!!!

题目:两个链表的第一个公共结点_牛客题霸_牛客网 (nowcoder.com)

题目的接口:

package main
import . "nc_tools"
/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */
/**
 * 
 * @param pHead1 ListNode类 
 * @param pHead2 ListNode类 
 * @return ListNode类
*/
func FindFirstCommonNode( pHead1 *ListNode ,  pHead2 *ListNode ) *ListNode {
    // write code here
}

解题思路:

这道题目也有个很巧妙的解法,怎么找到相交链表他们相交的地方呢?只要他们把自己和对方的路都走一遍,这样他们走的路程就是一样的,这样他们相交的地方就是链表的交汇点了~

代码:

package main
import . "nc_tools"
/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */
/**
 * 
 * @param pHead1 ListNode类 
 * @param pHead2 ListNode类 
 * @return ListNode类
*/
func FindFirstCommonNode( pHead1 *ListNode ,  pHead2 *ListNode ) *ListNode {
    l1 := pHead1
    l2 := pHead2
    for l1 != l2 {
        if l1 == nil {
            l1 = pHead2
        } else {
            l1 = l1.Next
        }
        if l2 == nil {
            l2 = pHead1
        } else {
            l2 = l2.Next
        }
    }
    return l1
}

过啦!!!

写在最后:

以上就是本篇文章的内容了,感谢你的阅读。

如果感到有所收获的话可以给博主点一个哦。

如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~

目录
打赏
0
0
0
0
339
分享
相关文章
|
4月前
LeetCode第二十四题(两两交换链表中的节点)
这篇文章介绍了LeetCode第24题的解法,即如何通过使用三个指针(preNode, curNode, curNextNode)来两两交换链表中的节点,并提供了详细的代码实现。
43 0
LeetCode第二十四题(两两交换链表中的节点)
|
4月前
Leetcode第十九题(删除链表的倒数第N个节点)
LeetCode第19题要求删除链表的倒数第N个节点,可以通过快慢指针法在一次遍历中实现。
54 0
Leetcode第十九题(删除链表的倒数第N个节点)
05_删除链表的倒数第N个节点
05_删除链表的倒数第N个节点
|
4月前
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
66 0
HashMap常见面试题(超全面):实现原理、扩容机制、链表何时升级为红黑树、死循环
HashMap常见面试题:红黑树、散列表,HashMap实现原理、扩容机制,HashMap的jd1.7与jdk1.8有什么区别,寻址算法、链表何时升级为红黑树、死循环
LeetCode第24题两两交换链表中的节点
这篇文章介绍了LeetCode第24题"两两交换链表中的节点"的解题方法,通过使用虚拟节点和前驱节点技巧,实现了链表中相邻节点的交换。
LeetCode第24题两两交换链表中的节点
04_两两交换链表中的节点
04_两两交换链表中的节点
|
6月前
|
【Leetcode刷题Python】剑指 Offer 22. 链表中倒数第k个节点
Leetcode题目"剑指 Offer 22. 链表中倒数第k个节点"的Python解决方案,使用双指针法找到并返回链表中倒数第k个节点。
68 5
【面试题】合井K个升序链表
【面试题】合井K个升序链表
41 0
【Java集合类面试十】、HashMap中的循环链表是如何产生的?
在多线程环境下,HashMap在扩容时如果发生条件竞争,元素的插入顺序可能形成循环链表,导致死循环。

热门文章

最新文章