Linked List
Two Pointers
Description
Given the head
of a singly linked list, return the middle node of the linked list .
If there are two middle nodes, return the second middle node.
Example 1:
Input: head = [1,2,3,4,5]
Output: [3,4,5]
Explanation: The middle node of the list is node 3.
Example 2:
Input: head = [1,2,3,4,5,6]
Output: [4,5,6]
Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.
Constraints:
The number of nodes in the list is in the range [1, 100]
.
1 <= Node.val <= 100
Solutions
Solution 1
Python3 Java C++ Go TypeScript Rust PHP C
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution :
def middleNode ( self , head : ListNode ) -> ListNode :
slow = fast = head
while fast and fast . next :
slow , fast = slow . next , fast . next . next
return slow
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 /**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode middleNode ( ListNode head ) {
ListNode slow = head , fast = head ;
while ( fast != null && fast . next != null ) {
slow = slow . next ;
fast = fast . next . next ;
}
return slow ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 /**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public :
ListNode * middleNode ( ListNode * head ) {
ListNode * slow = head , * fast = head ;
while ( fast && fast -> next ) {
slow = slow -> next ;
fast = fast -> next -> next ;
}
return slow ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14 /**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func middleNode ( head * ListNode ) * ListNode {
slow , fast := head , head
for fast != nil && fast . Next != nil {
slow , fast = slow . Next , fast . Next . Next
}
return slow
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 /**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function middleNode ( head : ListNode | null ) : ListNode | null {
let fast = head ,
slow = head ;
while ( fast != null && fast . next != null ) {
fast = fast . next . next ;
slow = slow . next ;
}
return slow ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 // Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
// pub val: i32,
// pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
// #[inline]
// fn new(val: i32) -> Self {
// ListNode {
// next: None,
// val
// }
// }
// }
impl Solution {
pub fn middle_node ( head : Option < Box < ListNode >> ) -> Option < Box < ListNode >> {
let mut slow = & head ;
let mut fast = & head ;
while fast . is_some () && fast . as_ref (). unwrap (). next . is_some () {
slow = & slow . as_ref (). unwrap (). next ;
fast = & fast . as_ref (). unwrap (). next . as_ref (). unwrap (). next ;
}
slow . clone ()
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31 /**
* Definition for a singly-linked list.
* class ListNode {
* public $val = 0;
* public $next = null;
* function __construct($val = 0, $next = null) {
* $this->val = $val;
* $this->next = $next;
* }
* }
*/
class Solution {
/**
* @param ListNode $head
* @return ListNode
*/
function middleNode($head) {
$count = 0;
$tmpHead = $head;
while ($tmpHead != null) {
$tmpHead = $tmpHead->next;
$count++;
}
$len = $count - floor($count / 2);
while ($count != $len) {
$head = $head->next;
$count--;
}
return $head;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 /**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode * middleNode ( struct ListNode * head ) {
struct ListNode * fast = head ;
struct ListNode * slow = head ;
while ( fast && fast -> next ) {
fast = fast -> next -> next ;
slow = slow -> next ;
}
return slow ;
}