leetcode876：求链表的中间结点

给定一个带有头结点 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 之间。
附leetcode地址：leetcode

遍历将节点放在数组中，然后取中间值

var middleNode = function (head) {
  if (!head) return []
  var arr = []
  while (head) {
    arr.push(head)
    head = head.next
  }
  return arr[Math.ceil((arr.length - 1) / 2)]
};

利用双指针，快指针走两步，慢指针走一步，快指针走完，慢指针则为中间值

var middleNode = function (head) {
  if (!head) return []
  var fast = slow = head
  while (fast && fast.next) {
    slow = slow.next
    fast = fast.next.next
  }
  return slow
};

快慢指针走一波

const getMiddleNode = function(head) {
    if(!head)  return null;

    let fast = head.next.next, slow = head.next;
    while(fast && fast.next) {
        fast = fast.next.next;
        slow = slow.next;
    }
    return slow;
};

都是快慢指针...

var middleNode = function(head) {
    let end = head, half = head 
    while(end.next) {
        end = end.next
        half = half.next
        if (!end.next) 
            break
        end = end.next
    }
    return half
};

解法：快慢指针

解题思路： 快指针一次走两步，慢指针一次走一步，当快指针走到终点时，慢指针刚好走到中间

const middleNode = function(head) {
    let fast = head, slow = head
    while(fast && fast.next) {
        slow = slow.next
        fast = fast.next.next
    }
    return slow
};

时间复杂度：O(n)

空间复杂度：O(1)

leetcode

快慢指针求解很简洁，赞

const middle_node = (node1) => {
  let fast = node1
  let slow = node1

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

function middleNode (head) {
let slow = head, fast = head
while (fast && fast.next) {
slow = slow.next
fast = fast.next.next
}
return slow
}

var middleNode = function(head) {
    // 定义快慢指针
    let slow = fast = head;
    while(fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
};

function middleNode(head: ListNode | null): ListNode | null {
    let p1 = head
    let p2 = head
    while(p2 && p2.next) {
        p1 = p1.next
        p2 = p2.next.next
    }
    return p1
};

Navigation Menu

Repository navigation

leetcode876：求链表的中间结点 #15

解法：快慢指针

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

leetcode876：求链表的中间结点 #15

Description

Activity

hecun0000 commented on Apr 13, 2020

liwuhou commented on Apr 13, 2020

mingju0421 commented on Apr 13, 2020

sisterAn commented on Apr 13, 2020

解法：快慢指针

fengmiaosen commented on Apr 21, 2020

Been101 commented on Jul 15, 2020

rookie-hhm commented on Jul 22, 2020

AnranS commented on Nov 17, 2020

RainyNight9 commented on Sep 27, 2023

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions