数据结构与算法 | Leetcode 876. middle-of-the-linked-list
原文链接: https://wangwei.one/posts/jav...
前面,我们实现了 删除单链表倒数第N个节点 操作,本篇来聊聊,如何求一个链表的中间节点。
求链表的中间结点
Leetcode 876. Middle of the Linked List
给定一个非空的单链表,要求返回它的中间节点,如果中间节点有两个则返回第二个。
例如:
Input: [1,2,3,4,5] Output: Node 3 from this list
Input: [1,2,3,4,5,6] Output: Node 4 from this list
解法一
第一种解法的思路比较容易想得到,先计算出链表的总长度,再计算出中间节点的下标,然后得遍历得到对应的节点即可。
代码
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode middleNode(ListNode head) { if(head == null){ return null; } int len = 0; for(ListNode curr = head; curr != null; ){ len++; curr = curr.next; } int targetIndex = 0; ListNode target = null; for(ListNode curr = head; curr != null; ){ if(targetIndex == len / 2){ target = curr; break; } targetIndex++; curr = curr.next; } return target; } }
解法二
第二种解法,使用快慢指针,让快指针的移动速度是慢指针的两倍,等到快指针到达终点时,慢指针恰好抵达中间节点。
一段小路上,A车行驶的速度是B车的两倍,等到A车到达终点时,B车恰好达到小路的中间位置。
代码
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode middleNode(ListNode head) { if(head == null){ return null; } ListNode slow = head; ListNode fast = head; for(ListNode curr = slow; slow != null; ){ if(fast == null || fast.next == null){ break; }else{ fast = fast.next.next; } slow = slow.next; } return slow; } }
到目前为止,我们已经使用快慢指针解决三个单链表相关的问题了:
单链表环检测
解法三
解法三也比较巧妙, 遍历单链表,只有当下标为奇数时,指针才向前移动,到最后,指针所指即为中间节点。
代码
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode middleNode(ListNode head) { if(head == null){ return null; } ListNode target = head; int index = 0; for(ListNode curr = head; curr != null; ){ if(index % 2 == 1){ target = target.next; } index++; curr = curr.next; } return target; } }
以上三种解法的时间复杂度均为O(n),在leetcode上的运行时间为 1ms,超过 82.96%
。
相关练习
参考资料
相关推荐
shenwenjie 2020-09-24
xiesheng 2020-08-02
mingyunxiaohai 2020-07-28
Cypress 2020-07-08
Cypress 2020-06-28
Dyancsdn 2020-06-27
Masimaro 2020-06-21
waitwolf 2020-06-21
Jasmineyaoyao 2020-06-16
OldBowl 2020-06-16
alicelmx 2020-06-16
Masimaro 2020-06-14
waitwolf 2020-06-08
nurvnurv 2020-06-05
ustbfym 2020-06-04
ziruoxiangyi 2020-06-03
范范 2020-06-03
Jasmineyaoyao 2020-05-31