【Day 25 】2023-07-04 - 876. 链表的中间结点

[azl397985856]

876. 链表的中间结点

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/middle-of-the-linked-list/

前置知识

暂无

题目描述

给定一个头结点为 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 之间。

[GuitarYs]

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def middleNode(head):
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    return slow

# 测试样例
head = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
node5 = ListNode(5)
head.next = node2
node2.next = node3
node3.next = node4
node4.next = node5

result = middleNode(head)
while result:
    print(result.val)
    result = result.next

[freesan44]

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func middleNode(_ head: ListNode?) -> ListNode? {
        var slow = head
        var fast = head

        while fast != nil && fast?.next != nil {
            fast = fast?.next?.next
            slow = slow?.next
        }

        return slow
    }
}

[zhaoygcq]

思路

快慢指针： 快指针一次走两步 慢指针一次走一步

代码

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var middleNode = function(head) {
    if(!head) return head;
    let slow = fast = head;
    while(fast && fast.next) {
        fast = fast.next.next;
        slow = slow.next;
    }
    return slow;
};

复杂度分析

• 时间复杂度：O(N)，其中 N 为数组长度。
• 空间复杂度：O(1)

[SoSo1105]

思路

定义快慢指针，同时从头结点开始向后遍历，快指针每次走两步，慢指针每次走一步，当快指针走到末尾结点时，慢指针恰好走到中间结点。

代码

class Solution:
    def middleNode(self, head):
        """
        :param head: ListNode
        :return: ListNode
        """
        fast = slow = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        return slow

复杂度分析

• 时间复杂度：O(N)
• 空间复杂度：O(1)

[954545647]

easy!

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var middleNode = function (head) {
  if (!head) return head
  let slow = fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow;
};

[jackgaoyuan]

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func middleNode(head *ListNode) *ListNode {
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    return slow
}

[Diana21170648]

思路

需要输出中间节点后面所有的内容，所以用快慢指针，一个走一步，一个走两步，如果要输出中间节点就可以用左右端点指针，一个指向头，一个指向尾

代码

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        #n=len(head)
        left=right=head
        #right=tail
        while right and right.next:
            left=left.next
            right=right.next.next
        return left

复杂度分析

• 时间复杂度：O(N)，其中 N 为链表长度。
• 空间复杂度：O(1)

[mo660]

思路

快慢指针

代码

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* low = head;
        ListNode* fast = head;
        while (fast != nullptr && fast->next != nullptr)
        {
            low = low->next;
            fast = fast->next->next;
        }
        return low;
    }
};

[snmyj]

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* cur=head;
        int cnt=0;
        while(cur!=NULL){
            cnt++;
            cur=cur->next;
        }
        cur=head;
        cnt=ceil(cnt/2);
        while(cnt!=0){
            cnt--;
            cur=cur->next;

        }
        return cur;
    }
};

[huizsh]

class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        slow = fast = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        return slow

[wzbwzt]

/* 思路： 双指针 slow走一步,fast走两步

复杂度： 时间复杂度：O(n) 空间复杂度：O(1) */

// Definition for singly-linked list.
type ListNode struct {
    Val  int
    Next *ListNode
}

func middleNode(head *ListNode) *ListNode {
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    return slow
}

[Alexno1no2]

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        fast ,slow = head , head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

[catkathy]

思路

快慢指针

Code

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

[jennyjgao]

public ListNode middleNode(ListNode head) {
        //快慢指针
        ListNode fast = head;
        ListNode slow = head;
        while(fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

[joemonkeylee]

function middleNode(head: ListNode | null): ListNode | null {
    if (head == null) {
        return null;
    }
    let slow = head;
    let fast = head;

    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
};

[jameswangxin]

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        auto p = head, q = head;
        while (q && q->next) {
            q = q->next;
            p = p->next;
            if (q) q = q->next;
        }
        //cout << p->val << endl;
        return p;
    }
};

[liuajingliu]

解题思路

双指针

代码实现

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var middleNode = function (head) {
  let slow = (fast = head);
  while (slow && fast && fast.next) {
    fast = fast.next.next;
    slow = slow.next;
  }
  return slow;
};

复杂度分析

• 时间复杂度: $O(N)$

• 空间复杂度: $O(1)$

[Moin-Jer]

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

[Beanza]

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

[Fuku-L]

代码

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

[passengersa]

代码： /**

• @param {ListNode} head

• @return {ListNode} */ var middleNode = function(head) { let fast = head; let slow = head;

  while (fast && fast.next) { fast = fast.next.next; slow = slow.next; }

  return slow; };

[yzhyzhyzh123]

思路

快慢指针

代码

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

[yetfan]

代码

class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow