快慢指针找链表中间节点的完整代码
时间: 2024-03-25 22:16:12 浏览: 14
以下是快慢指针找链表中间节点的完整代码:
```java
public ListNode middleNode(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
```
希望能对您有所帮助,还有什么其它问题我可以帮您解答吗?
相关问题
快慢指针找链表中间节点的完整代码C语言
好的,以下是找链表中间节点的完整代码C语言:
```
#include <stdio.h>
#include <stdlib.h>
typedef struct ListNode {
int val;
struct ListNode *next;
} ListNode;
ListNode* middleNode(ListNode* head) {
ListNode *fast = head;
ListNode *slow = head;
while (fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
int main() {
ListNode *head = (ListNode*) malloc(sizeof(ListNode));
head->val = 1;
head->next = (ListNode*) malloc(sizeof(ListNode));
head->next->val = 2;
head->next->next = (ListNode*) malloc(sizeof(ListNode));
head->next->next->val = 3;
head->next->next->next = (ListNode*) malloc(sizeof(ListNode));
head->next->next->next->val = 4;
head->next->next->next->next = (ListNode*) malloc(sizeof(ListNode));
head->next->next->next->next->val = 5;
head->next->next->next->next->next = NULL;
ListNode *middle = middleNode(head);
printf("%d\n", middle->val);
return 0;
}
```
笑话:为什么Java程序员喜欢喝茶?因为Java里有泡茶的类!
寻找链表中间节点华为od
为了找到链表的中间节点,我们可以使用快慢指针的方法。
快慢指针思路是让一个指针(快指针)每次向前移动两个节点,另一个指针(慢指针)每次向前移动一个节点,直到快指针到达链表末尾。这样,快指针遍历完链表时,慢指针就恰好到达链表的中间节点。
具体的实现步骤如下:
1. 初始化快指针和慢指针,都指向链表的头节点。
2. 使用一个循环,每次循环时,快指针向前移动两个节点,慢指针向前移动一个节点。
3. 当快指针到达链表末尾时,慢指针就到达了链表的中间节点。
4. 返回慢指针指向的节点(即中间节点)。
示例代码如下:
```python
def find_middle_node(head):
slow_ptr = head
fast_ptr = head
while fast_ptr is not None and fast_ptr.next is not None:
slow_ptr = slow_ptr.next
fast_ptr = fast_ptr.next.next
return slow_ptr
```
以上方法的时间复杂度是 O(n),其中 n 是链表的长度。这是因为快指针每次移动两个节点,所以它最多需要遍历链表的一半。