LeetCode【876.链表的中间结点】

一时失言乱红尘 2022-05-16 05:05 130阅读 0赞

### 题目描述 ###

> 给定一个带有头结点`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 ####

通过 w h i l e while while循环统计链表中变量的个数即`count`，再次进行遍历时，直接返回第 c o u n t 2 + 1 \\frac\{count\}\{2\}+1 2count\+1结点即可,当用 c o u n t count count循环再次开始遍历时， q N o d e qNode qNode本身已经是 h e a d head head,所以再移动 c o u n t 2 \\frac\{count\}\{2\} 2count次时，此时的 q N o d e qNode qNode已经是第 c o u n t 2 + 1 \\frac\{count\}\{2\}+1 2count\+1结点。

#### 代码 1 ####

class Solution { public ListNode middleNode(ListNode head) { int count = 0; ListNode pNode = head, qNode = head; while(pNode != null) { count ++; pNode = pNode.next; } count = count / 2 ; while(count != 0) { count --; qNode = qNode.next; } return qNode; } }

#### 复杂度分析： ####

*  时间复杂度： O ( N ) O(N) O(N),其中N是列表中的结点数目。
 *  空间复杂度： O ( 1 ) O(1) O(1),qNode,pNode用去的空间。

--------------------

#### 思路2 ####

按顺序将每个结点放到数组A中，然后中间结点就是**A\[A.length/2\]**,因此我们可以通过索引检索每个结点。由于索引是从0开始的，所以中间节点的位置即是 A \[ A . l e n g t h / 2 \] A\[A.length/2\] A\[A.length/2\].

#### 代码2 ####

class Solution { public ListNoe[] A = new ListNode[100]; int t = 0; while(head.next != null) { A[t++] = head; head = head.next; } return A[t/2]; }

#### 复杂度分析 ####

*  时间复杂度： O ( N ) O(N) O(N),其中N是列表中的结点数目。
 *  空间复杂度： O ( N ) O(N) O(N),A用去的空间。

--------------------

#### 思路3 ####

当用慢指针**slow**遍历列表时，让另一个指针**fast**的速度是**slow**的二倍，则当快指针到结尾时，**slow**指针位于中间。初始位置都为**head**时，当**fast**指向最终的**null**时，**slow**也就达到了要求。

class Solution { public ListNode middleNode(ListNode head) { ListNode slow = head, fast = head; while((fast != null) && (fast.next != null)) { slow = slow.next; fast = fast.next.next; } return slow; } }

#### 复杂度分析 ####

*  时间复杂度： O ( N ) O(N) O(N),其中N是列表中的结点数目。
 *  空间复杂度： O ( 1 ) O(1) O(1),fast,slow用去的空间。

#### 完整代码 ####

package cn.zcs.leetcode; import java.io.*; class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } class Solution { public ListNode middle (ListNode head) { if(head == null) return head; ListNode fast = head, slow = head; while(fast.next != null && fast != null) { slow = slow.next; fast = fast.next.next; } return slow; } } public class middleNode { public static int[] stringToIntegerArray(String input) { input = input.trim(); input = input.substring(1, input.length() - 1); if(input.length() == 0) { return new int[0]; } String[] parts = input.split(","); int[] output = new int[parts.length]; for(int index = 0; index < parts.length; index ++) { String part = parts[index].trim(); output[index] = Integer.parseInt(part); } return output; } public static ListNode stringToListNode(String input) { int[] nodeValues = stringToIntegerArray(input); ListNode dummyRoot = new ListNode(0); ListNode ptr = dummyRoot; for(int item : nodeValues) { ptr.next = new ListNode(item); ptr= ptr.next; } return dummyRoot.next; } public static String listNodeToString(ListNode node) { if(node == null) { return "[]"; } String result = ""; while(node != null) { result += Integer.toString(node.val) + ", "; node = node.next; } return "[" + result.substring(0, result.length() - 2) + "]"; } public static void main(String[] args) throws IOException { // TODO Auto-generated method stub BufferedReader in = new BufferedReader (new InputStreamReader(System.in)); String line; while((line = in.readLine()) != null) { ListNode head = stringToListNode(line); ListNode ret = new Solution().middle(head); String out = listNodeToString(ret); System.out.println(out); } } }