C#LeetCode刷题之#876-链表的中间结点（Middle of the Linked List）

问题

给定一个带有头结点 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

输入：[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.

输入：[1,2,3,4,5,6]

输出：此列表中的结点 4 (序列化形式：[4,5,6])

由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

提示：

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

Given a non-empty, singly linked list with head node head, return a middle node of linked list.

If there are two middle nodes, return the second middle node.

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

Output: Node 3 from this list (Serialization: [3,4,5])

The returned node has value 3. (The judge's serialization of this node is [3,4,5]).Note that we returned a ListNode object ans, such that:ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL.

Input: [1,2,3,4,5,6]

Output: Node 4 from this list (Serialization: [4,5,6])

Since the list has two middle nodes with values 3 and 4, we return the second one.

Note:

The number of nodes in the given list will be between 1 and 100.

示例

public class Program {

    public static void Main(string[] args) {

        var head = new ListNode(1) {

            next = new ListNode(2) {

                next = new ListNode(3) {

                    next = new ListNode(4)

                }

            }

        };

        var res = MiddleNode(head);

        ShowArray(res);

        res = MiddleNode2(head);

        ShowArray(res);

        Console.ReadKey();

    }

    private static void ShowArray(ListNode list) {

        var node = list;

        while(node != null) {

            Console.Write($"{node.val} ");

            node = node.next;

        }

        Console.WriteLine();

    }

    private static ListNode MiddleNode(ListNode head) {

        //暴力解法

        var count = 0;

        var node = head;

        while(node != null) {

            count++;

            node = node.next;

        }

        var mid = count / 2;

        node = head;

        var index = 0;

        while(node != null && index++ < mid) {

            node = node.next;

        }

        return node;

    }

    private static ListNode MiddleNode2(ListNode head) {

        //快慢双指针

        var slow = head;

        var fast = head;

        while(fast != null && fast.next != null) {

            fast = fast.next.next;

            slow = slow.next;

        }

        return slow;

    }

    public class ListNode {

        public int val;

        public ListNode next;

        public ListNode(int x) { val = x; }

    }

}

以上给出2种算法实现，以下是这个案例的输出结果：

3 4

3 4

分析：

显而易见，以上2种算法的时间复杂度均为： $O(n)$ 。

巴特西

C#LeetCode刷题之#876-链表的中间结点（Middle of the Linked List）

最新文章

热门文章