数据结构——链表的中间结点（LeetCode876）

给定一个带有头结点head的非空单链表返回链表的中间结点。如果有两个中间结点则返回第二个中间结点。示例1输入[1

给定一个带有头结点 head 的非空单链表返回链表的中间结点。如果有两个中间结点则返回第二个中间结点。

示例1

输入[1,2,3,4,5]输出此列表中的结点 3 (序列化形式[3,4,5])返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。]

示例2

输入[1,2,3,4,5,6]输出此列表中的结点 4 (序列化形式[4,5,6])由于该列表有两个中间结点值分别为 3 和 4我们返回第二个结点。

思想

双指针遍历

一个指针p1每次走两步另外一个指针p2每次走一步

p1 先走p1走两步p2紧跟着走一步。 分为两种情况 1如果链表结点数为偶数则当p1指向空时返回此时的 p2 2如果链表结点数为奇数当p1.next null 时返回此时的 p2. 如图所示

具体实现

考虑所给链表为空时或者只有一个结点直接返回 head

链表不为空时先定义变量 1定义 cur 变量表示当前变量 2定义 p1 表示每次走2步的引用指针 3定义 p2 表示每次走1 步的引用指针

对原链表进行双引用遍历 1分链表结点为偶数 和 链表长度为 奇数 两种情况考虑因此有两个判断条件只要不满足其中任何一个条件就是找到中间结点。 所以遍历条件为 (p1 ! null null) (2)每次循环两个引用的增进 p1 p1.next.next; p2 p2.next;

返回中间结点 代码实现

package www.fanfan.com;/*** author:kelly_fanfan*///返回链表的中间结点public class LeetCode876 {class ListNode{private int val;private ListNode next;public ListNode(int val){this.val val;this.next null;}}class Solution {public ListNode middleNode(ListNode head) {if(head null || head.next null){return head;}ListNode cur1 head;ListNode cur2 head;while (cur1 ! null null){cur1 cur1.next.next;cur2 cur2.next;}return cur2;}}}