您现在的位置是：首页 > 后台技术 > 数据结构与算法数据结构与算法

链表的中间节点(图文)

第十三双眼睛2024-01-23【数据结构与算法】人已围观

简介链表的中间节点
给你单链表的头结点 head ，请你找出并返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

思路：先将链表遍历一遍，统计链表的长度，然后第二遍遍历，遍历一半的长度，即可找到链表的中间节点，不过要注意链表长度是奇数还是偶数。代码如下：

public static ListNode method1(ListNode head) {
   if (head == null) {
       return null;
   }
   int count = 0;
   ListNode p = head;
   while (p != null) {
       count ++;
       p = p.next;
   }
   int i = 1;
   p = head;
   while (i <= (count / 2)) {
       p = p.next;
       i ++;
   }
   return p;
}

思路2：
先遍历一遍链表，将元素存储到列表中，然后利用列表下标访问的特性，即可获得链表中间元素。代码略。
思路3：
定义两个指针，一个指针每次移动一步，另一个指针每次移动两步，当快指针移动到末尾的时候，慢指针刚好在中间。代码如下：

public static ListNode method2(ListNode head) {
   if (head == null) {
       return null;
   }
   ListNode slow = head;
   ListNode fast = head;
   while (fast != null && fast.next != null) {
       slow = slow.next;
       fast = fast.next.next;
   }
   return slow;
}

Tags：

很赞哦！ ()

上一篇：回文链表(图文)

下一篇：栈实现队列(图文)