链表中的中间结点-算法练习总结

算法题目

链表中的中间节点：

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

示例 1：

   输入:[1,2,3,4,5]
    输出：此列表中的结点 3 (序列化形式：[3,4,5])
    返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
    注意，我们返回了一个 ListNode 类型的对象 ans，这样：
    ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

示例 2：

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

提示：

给定链表的结点数介于 1 和 100 之间。

测试用例

[3,4,5] [2] [1,2,3,4]

思路分析

解法一：根据链表长度

? 思路：首先遍历链表得到链表的长度，根据链表长度再次遍历得到中间结点
? 分析：时机复杂度为n级，不需额外的空间，但是会遍历一次半链表

解法二：双指针法

? 思路：利用两个指针，一个快指针，一个慢指针，慢的每次后移一次，快的每次后裔两次，当快指针遍历结束返回慢指针
? 分析：时间复杂度为n级，不需要额外的内存空间
? 思考：由于链表的长度为偶数或者奇数，所以在快慢指针移动上面要注意这一点的处理

//测试函数
import com.test.day6_22.ListNode;

/**

@author cosefy

@date 2020/6/23
*/
public class GetMiddleNode {
public static void main(String[] args) {
    int[] nums = {1, 3, 4, 5};
    ListNode head = getLinkedList(nums);
    ListNode middle_node1 = test1(head);
    ListNode middle_node2 = test2(head);


?        System.out.println("解法一的中间结点结果：" + middle_node1.val);
?        System.out.println("解法二的中间结点结果：" + middle_node2.val);

?    }

?    //根据数组创建链表，返回头结点
?    public static ListNode getLinkedList(int[] nums) {
?        ListNode head = new ListNode(nums[0]); //链表长度在1-100之间
?        ListNode L = head;
?        for (int i = 1; i < nums.length; i++) {
?            ListNode node = new ListNode(nums[i]);
?            L.next = node;
?            L = L.next;
?        }
?        return head;
?    }
}

    //解法一：根据链表长度
    public static ListNode test1(ListNode head) {
        int count = 0;
        ListNode L = head;
        while (L != null) {
            ++count;
            L = L.next;
        }
        count = count / 2 + 1;
        while (count > 1) {
            head = head.next;
            --count;
        }
        return head;
    }

    //解法二：双指针
?    public static ListNode test2(ListNode head) {
?        ListNode fast_node = head, slow_node = head;
?        while (fast_node.next != null) {
?            fast_node = fast_node.next;
?            slow_node = slow_node.next;  //这里的处理方式是先让快指针移动，再慢指针，再快指针。
?            if (fast_node.next != null)
?                fast_node = fast_node.next;

?        }
?        return slow_node;
?    }

链表中的中间结点-算法练习总结

原文：https://www.cnblogs.com/cosefy/p/13182500.html