如何通过仅遍历整个列表一次来找到链表中的中间元素？
列表的长度没有给出，我只能使用两个指针。如何才能做到这一点？
问问题
44085 次
14 回答
31
除非您知道长度，否则我不知道如何在不遍历整个列表的情况下做到这一点。
我猜答案是希望一个指针一次遍历一个元素，而第二个指针一次移动 2 个元素。
这样，当第二个指针到达末尾时，第一个指针将位于中间。
于 2013-05-08T17:09:09.147 回答
12
下面的代码将帮助您获得中间元素。您需要使用“快”和“慢”两个指针。在每一步，快速指针将递增 2，较慢指针将递增 1。当列表结束时，慢速指针将位于中间。
让我们考虑一下Node这样的外观
class Node
{
int data;
Node next;
}
而LinkedList有一个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
于 2013-05-09T04:18:37.113 回答
1
在 C 中，为了完整性，使用指针。请注意，这是基于用于检查链表是否包含循环的“龟兔赛跑”算法。
我们的节点定义如下：
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）。
于 2014-06-22T14:06:53.070 回答
0
对于具有指向头节点和尾节点的给定指针的双向链表：
我们可以同时使用头和尾遍历：
p = head;
q = tail;
while(p != q && p->next != q)
{
p = p->next;
q = q->prev;
}
return p;
引入一个指向中间节点的指针可能是一种选择，但是像 insertNode 和 deleteNode 这样的函数必须修改这个指针。
于 2018-12-27T08:56:26.537 回答
0
使用大小变量，您可以保持链接列表的大小。
public class LinkedList {
private Node headnode;
private int size;
public void add(int i) {
Node node = new Node(i);
node.nextNode = headnode;
headnode = node;
size++;
}
public void findMiddleNode(LinkedList linkedList, int middle) {
Node headnode = linkedList.getHeadnode();
int count = -1;
while (headnode != null) {
count++;
if(count == middle) {
System.out.println(headnode.data);
}else {
headnode = headnode.nextNode;
}
}
}
private class Node {
private Node nextNode;
private int data;
public Node(int data) {
this.data = data;
this.nextNode = null;
}
}
public Node getHeadnode() {
return headnode;
}
public int getSize() {
return size;
}
}
然后从客户端方法中找到列表的中间大小：
public class MainLinkedList {
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
linkedList.add(5);
linkedList.add(3);
linkedList.add(9);
linkedList.add(4);
linkedList.add(7);
linkedList.add(99);
linkedList.add(34);
linkedList.add(798);
linkedList.add(45);
linkedList.add(99);
linkedList.add(46);
linkedList.add(22);
linkedList.add(22);
System.out.println(linkedList.getSize());
int middle = linkedList.getSize()/2;
linkedList.findMiddleNode(linkedList, middle);
}
}
我不知道这是否比两个节点的方式更好，但在这里你也不必遍历整个循环。
于 2017-03-21T09:03:52.003 回答
0
下面的 Java 方法查找链表的中间部分。它使用两个指针：
- 每次迭代中移动一个的慢速指针。
- 在每次迭代中移动两次的快速指针。
当 fast 到达链表末尾时，slow 指针会指向中间
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;
}
于 2018-04-23T09:16:18.120 回答
0
使用两指针方法的中间元素的 Python 代码：
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def printList(self):
temp = self.head
while(temp):
print(temp.data, end=" ")
temp = temp.next
def insertAtBeg(self, new_data):
new_node = Node(new_data)
if self.head is None:
self.head = new_node
return
new_node.next = self.head
self.head = new_node
def findMiddle(self):
fast_ptr = self.head
slow_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 ' + str (slow_ptr.data))
if __name__ == '__main__':
mylist = LinkedList()
mylist.insertAtBeg(10)
mylist.insertAtBeg(20)
mylist.insertAtBeg(30)
mylist.findMiddle()
输出：
中间元素是
于 2019-01-18T11:59:06.880 回答
0
有两种可能的答案，一种是奇数，一种是偶数，都具有相同的算法
对于奇数：一个指针移动一步，第二个指针一次移动两个元素，当第二个元素到达最后一个元素时，第一个指针所在的元素，中间元素。很容易奇怪。尝试：1 2 3 4 5
对于偶数：相同，一个指针移动一步，第二个指针移动两个元素，当第二个元素不能跳转到下一个元素时，第一个指针所在的元素，中间元素。尝试：1 2 3 4
于 2015-08-10T04:17:59.337 回答
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));
}
}
于 2019-03-27T10:21:16.527 回答
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);
于 2016-06-18T12:37:42.243 回答
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);
}
}
}
}
于 2019-04-27T03:57:17.977 回答
0
类节点：
# Function to initialise the node object
def __init__(self, data):
self.data = data
self.next = None
类链表：
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()
于 2020-03-09T11:42:19.667 回答
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;
}
于 2017-07-24T15:14:06.850 回答
-2
使用“fast”和“slow”两个指针是愚蠢的，因为操作符 next 被使用了 1.5n 次。没有优化。
使用指针保存中间元素可以帮助您：
list* find_mid_1(list* ptr)
{
list *p_s1 = ptr, *p_s2 = ptr;
while (p_s2=p_s2->get_next())
{
p_s2 = p_s2->get_next();
if (!p_s2)
break;
p_s1 = p_s1->get_next();
}
return p_s1;
}
于 2016-06-13T02:45:04.637 回答