如何在遍历整个链表一次的情况下，通过只使用两个指针找到链表中间元素？
这个链表的长度是未知的。该怎么做？
14个回答
31
我不认为在不知道链表长度的情况下可以避免遍历整个链表。
我的猜测是，答案希望一个指针一次遍历一个元素，而第二个指针每次移动2个元素。
这样当第二个指针到达末尾时，第一个指针将在中间位置。
- Jean-Bernard Pellerin
2
但是我想知道它是否适用于链表中奇数和偶数个元素...？ - RAM
在纸上尝试使用1、2、3、4、5个元素，你会注意到它的规律以及它是如何/为什么工作的。 - Jean-Bernard Pellerin
12
以下代码可以帮助您获取中间元素。您需要使用两个指针"fast"和"slow"。在每一步中，快指针将增加两个，慢指针将增加一个。当列表结束时，慢指针将在中间位置。
让我们考虑节点的外观如下：
让我们考虑节点的外观如下：
class Node
{
int data;
Node next;
}
而链表具有一个getter方法，用于提供链表的头部
public Node getHead()
{
return this.head;
}
以下方法将获取列表的中间元素（不知道列表大小）
public int getMiddleElement(LinkedList l)
{
return getMiddleElement(l.getHead());
}
private int getMiddleElement(Node n)
{
Node slow = n;
Node fast = n;
while(fast!=null && fast.next!=null)
{
fast = fast.next.next;
slow = slow.next;
}
return slow.data;
}
示例：
如果列表是1-2-3-4-5，则中间元素为3。
如果列表是1-2-3-4，则中间元素为3。
- asifsid88
2
在 C 语言中，使用指针来实现完整性。请注意，这是基于 "Tortoise and Hare" 算法的思路，用于检查链表是否包含循环。
那么我们的算法如下：
对于节点数为偶数的列表，这将返回紧接实际中心的节点（例如，在具有10个节点的列表中，这将返回第6个节点）。
我们的节点定义如下：
typedef struct node {
int val;
struct node *next;
} node_t;
那么我们的算法如下：
node_t *
list_middle (node_t *root)
{
node_t *tort = root;
node_t *hare = root;
while (hare != NULL && hare->next != NULL) {
tort = tort->next;
hare = hare->next->next;
}
return (tort);
}
对于节点数为偶数的列表，这将返回紧接实际中心的节点（例如，在具有10个节点的列表中，这将返回第6个节点）。
- Richard Horrocks
0
以下Java方法可以找到链表的中间位置。它使用了两个指针：
- 慢指针，在每次迭代中移动一个节点。
- 快指针，在每次迭代中移动两个节点。
当快指针达到链表末尾时，慢指针将指向链表的中间位置。
public SinglyLinkedListNode getMiddle(SinglyLinkedListNode list) {
if (list == null)
return null;
SinglyLinkedListNode fastPtr = list.next;
SinglyLinkedListNode slowPtr = list;
while (fastPtr != null) {
fastPtr = fastPtr.next;
if (fastPtr != null) {
slowPtr = slowPtr.next;
fastPtr = fastPtr.next;
}
}
return slowPtr;
}
- Debapriya Biswas
0
LinkedList.Node current = head;
int length = 0;
LinkedList.Node middle = head;
while(current.next() != null){
length++;
if(length%2 ==0){
middle = middle.next();
}
current = current.next();
}
if(length%2 == 1){
middle = middle.next();
}
System.out.println("length of LinkedList: " + length);
System.out.println("middle element of LinkedList : " + middle);
- Laila Al-Saadi
0
使用C#来找到链表的中间元素：
static void Main(string[] args)
{
LinkedList<int> linked = new LinkedList<int>();
linked.AddLast(1);
linked.AddLast(3);
linked.AddLast(5);
linked.AddLast(6);
linked.AddFirst(12);
Console.WriteLine("Middle Element - " + ListMiddle<int>(linked));
Console.ReadLine();
}
public static T ListMiddle<T>(IEnumerable<T> input)
{
if (input == null)
return default(T);
var slow = input.GetEnumerator();
var fast = input.GetEnumerator();
while (slow.MoveNext())
{
if (fast.MoveNext())
{
if (!fast.MoveNext())
return slow.Current;
}
else
{
return slow.Current;
}
}
return slow.Current;
}
- ravithejag
0
import java.util.*;
public class MainLinkedList {
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
linkedList.add(10);
linkedList.add(32);
linkedList.add(90);
linkedList.add(43);
linkedList.add(70);
linkedList.add(20);
linkedList.add(45);
int middle = linkedList.size()/2;
System.out.println(linkedList.get(middle));
}
}
- Arun Shinde
0
我正在添加我的解决方案，它适用于奇数和偶数个元素的情况，例如：
1-2-3-4-5 中间元素为3
1-2-3-4 中间元素为2,3
这个解决方案受到了帖子中其他答案提到的快指针和慢指针原理的启发。
public class linkedlist {
Node head;
static class Node {
int data;
Node next;
Node(int d) { data = d; next=null; }
}
public static void main(String args[]) {
linkedlist ll = new linkedlist();
Node one = new Node(1);
Node second = new Node(2);
Node third = new Node(3);
Node fourth = new Node(4);
Node five = new Node(5);
Node sixth = new Node(6);
Node seventh = new Node(7);
Node eight = new Node(8);
ll.head = one;
one.next = second;
second.next = third;
third.next = fourth;
fourth.next = five;
five.next = sixth;
sixth.next = seventh;
seventh.next = eight;
ll.printList();
ll.middleElement();
}
public void printList() {
Node n = head;
while(n != null) {
System.out.print(n.data + " ---> ");
n = n.next;
}
}
public void middleElement() {
Node headPointer = head;
Node headFasterPointer = head;
int counter = 0;
if(head != null) {
while(headFasterPointer.next != null) {
if(headFasterPointer.next.next != null) {
headFasterPointer = headFasterPointer.next.next;
headPointer = headPointer.next;
}
else
{
headFasterPointer = headFasterPointer.next;
}
counter++;
}
System.out.println();
System.out.println("The value of counter is " + counter);
if(counter %2 == 0) {
System.out.println("The middle element is " + headPointer.data + "," + headPointer.next.data);
}
else
{
System.out.println("The middle element is " + headPointer.data);
}
}
}
}
- Vaibhav S
0
有两种可能的答案，一种是针对奇数，另一种是针对偶数，两者都具有相同的算法
对于奇数：一个指针每次移动一步，第二个指针每次移动两个元素，当第二个元素到达最后一个元素时，第一个指针所在的元素就是中间元素。对于奇数来说非常容易。 尝试：1 2 3 4 5
对于偶数：同样地，一个指针每次移动一步，第二个指针每次移动两个元素，当第二个元素无法跳到下一个元素时，第一个指针所在的元素就是中间元素。 尝试：1 2 3 4
- Rushabh Shah
0
类 Node：
# Function to initialise the node object
def __init__(self, data):
self.data = data
self.next = None
链表类 LinkedList：
def __init__(self):
self.head = None
def push(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
# Function to get the middle of
# the linked list
def printMiddle(self):
slow_ptr = self.head
fast_ptr = self.head
if self.head is not None:
while (fast_ptr is not None and fast_ptr.next is not None):
fast_ptr = fast_ptr.next.next
slow_ptr = slow_ptr.next
print("The middle element is: ", slow_ptr.data)
驱动程序代码
list1 = LinkedList()
list1.push(5)
list1.push(4)
list1.push(2)
list1.push(3)
list1.push(1)
list1.printMiddle()
- mahesh chougule
1
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接