【Day 25 】2022-01-05 - 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 之间。

[callmeerika]

思路

利用快慢指针

代码

var middleNode = function(head) {
    let p = head;
    let q = head;
    while(q&&q.next) {
        p = p.next;
        q = q.next.next;
    }
    return p;
};

复杂度

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

[Toms-BigData]

【Day 25】876. 链表的中间结点

思路

快慢指针

golang代码

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

复杂度

时间:O(n) 空间:O(1)

[1149004121]

876. 链表的中间结点

思路

典型的快慢指针题，唯一要注意的是奇节点个数和偶节点个数的情况要分类讨论。

代码

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

复杂度分析

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

[charlestang]

思路

使用快慢指针，快指针每次走两步，慢指针每次走一步，当快指针到尾部时候，慢指针正好指向中间点。

代码

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

时间复杂度 O(n)

空间复杂度 O(1)

[lilililisa1998]

class Solution(object): def middleNode(self, head): """ :type head: ListNode :rtype: ListNode """ p=head num=0 while p!=None: num+=1 p=p.next num/=2 while num>0: head=head.next num-=1 return head

[KevinWorkSpace]

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;
    }
}

[ZZRebas]

思路

快慢指针，快指针每次走 2 步，慢指针每次走 1 步，当快指针走到末尾的时候，慢指针刚好到达链表中点。

代码(Python)

class ListNode(object):
    def __init__(self,data,next=None):
        self.data=data
        self.next=next

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

linklist=[1,2,3,4,5]
# node6=ListNode(6,None)
node5=ListNode(5,None)
node4=ListNode(4,node5)
node3=ListNode(3,node4)
node2=ListNode(2,node3)
node1=ListNode(1,node2)
head=ListNode(None,node1)

obj=Solution()
print(obj.middleNode(head).data)    #3

复杂度分析

• 时间复杂度：O(N)，N为链表节点数。
• 空间复杂度：

[gova-i267]

题目

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

思路

• 先计算链表的长度
• 然后取中间数
• 让头节点移动中间数个节点
• 返回头结点

Java代码

class Solution {
    public ListNode middleNode(ListNode head) {
        int n = 0;
        ListNode temp = head;
        while (temp != null) {
            n++;
            temp = temp.next;
        }
        n /= 2;
        for (int i=0;i<n;i++) {
            head=head.next;
        }
        return head;
    }
}

复杂度分析

• 时间复杂度 O(n)
• 空间复杂度 O(1）

[Davont]

思路

快慢指针

Code

/**
 * 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) {
    <!-- 声明快慢指针 -->
    let fast = slow = head
    <!-- 当快指针和快指针的下一个节点都存在的时候进入循环 -->
    while(fast && fast.next) {
        <!-- 慢指针一次走一步，快指针一次走两步 -->
        slow = slow.next
        fast = fast.next.next
    }
    <!-- 返回slow -->
    return slow
};

[RocJeMaintiendrai]

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(1)

[GoRedFish]

代码

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

[biscuit279]

思路：

快慢指针，快指针每次两步，慢指针每次一步，则快指针走到头慢指针刚好在中间

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        slow,fast =head,head
        while fast and fast.next:
            fast= fast.next.next
            slow = slow.next
        return slow

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

[tongxw]

思路

链表常识题。

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

        return slow;
    }
}

TC: O(N), SC: O(1)

[JudyZhou95]

思路

快慢指针

代码

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

复杂度

TC: O(N)

SC: O(1)

[tangjy149]

思路

快慢指针，fast走的路程=slow路程*2，从而fast到结尾，slow到中间节点

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        if(head==nullptr) return nullptr;
        ListNode* fast=head;
        ListNode* slow=head;
        while(fast!=nullptr&&fast->next!=nullptr){
            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, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

复杂度分析

---

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

[arteecold]

双指针 跟书上的例子很像

[577961141]

题目思路

采用快慢指针的形式求解

题目的题解code

/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val = 0, $next = null) {
 *         $this->val = $val;
 *         $this->next = $next;
 *     }
 * }
 */
class Solution {

    /**
     * @param ListNode $head
     * @return ListNode
     */
    function middleNode($head) {
        $slow = $feat = $head;

        while($slow && $feat && $feat->next) {
            $feat = $feat->next->next;
            $slow = $slow->next;
        }

        return $slow;
    }
}

时间和空间复杂度

• 时间复杂度：O(n)，n为链表的长度
• 空间复杂度：O(1)，只需要$feat和$slow的存储空间

[Alexno1no2]

# 题解
# 使用slow,fast两个指针,slow每次走一步,fast每次走2步
# 当fast走到底时，slow就是走到了链表的中间节点
# 复杂度 O(N)

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

[uniqlell]

 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }

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

[Myleswork]

思路

快慢指针

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* slow;
        ListNode* fast;
        slow = fast = head;
        while(fast && fast->next){
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(1)

[junbuer]

思路

• 快慢指针

  slow一次移动一个节点，fast一次移动两个节点，当fast指向None时返回slow指向的节点

代码

class Solution(object):
    def middleNode(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        s = f = head
        while f and f.next:
            f = f.next.next
            s = s.next
        return s

复杂度分析

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

[sujit197]

快慢指针

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;

    }
}

[cszys888]

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

time complexity: O(N) space complexity: O(1)

[q815101630]

快慢指针

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        fast = slow = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next

        return slow

时间 O(n) 空间 O(1)

[bubblefu]

思路

1. 取到链表的中间节点，可直接想到用快慢指针的方式，快指针一次走两下，慢指针一次走一下
2. 当快指针走完链表后，慢指针即可走到中间（奇数时）或两个中间的后一个（偶数时）
3. 为了实现2，需设置终止条件为，当快指针走到倒数第二个数的时候，再次走，才是最后一次走

代码 Java

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

}

}

> ### 复杂度分析

1. 时间复杂度 O N  N为链表的长度，快指针需要遍历完整个链表
2. 空间复杂度 O 1

[noperoc]

思路

• 快慢双指针找中点，慢指针是中点

关键点

代码

• 语言支持：Java

Java Code:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
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;
    }
}

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

[chenyaohn]

思路

快慢双指针

代码

 public ListNode middleNode(ListNode head) {

        ListNode slow = head;
        ListNode fast = head;
        while (fast!=null && fast.next!=null){
            fast = fast.next!=null?fast.next.next:null;
            slow = slow.next;
        }
        return slow;
    }

复杂度分析

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

[hx-code]

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

[ACcentuaLtor]

简单题重拳出击（不是) 快慢指针：时间复杂度O(n)，空间复杂度O(1)

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

[jackshengMan]

思路

快慢指针

语言

java

public class Solution {

    public ListNode middleNode(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;

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

复杂度分析

时间复杂度 O(n) 空间复杂度 O(1)

[alongchong]

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

[xiao-xiao-meng-xiang-jia]

class Solution { public ListNode middleNode(ListNode head) { ListNode pre = head; int n = 0; while(pre !=null){ pre=pre.next; n++; } int k=0; pre=head; while(k<(n/2)){ k++; pre = pre.next; } return pre; } } 时间复杂度：O(N); 空间复杂度：O(1);

[didiyang4759]

定义两个快慢指针

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(1)

[Tiquiero]

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

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

[kite-fly6618]

思路

快慢指针

代码

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

复杂度

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

[YuyingLiu2021]

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
#思路：双指针： 快慢
        left = right = head

        while right.next and right.next.next:
            right = right.next.next
            left = left.next
        if not right.next:
            return left
        else:
            return left.next

[ywang525]

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

[testeducative]

思路

快慢指针

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        if(head == NULL)
            return NULL;
        ListNode* first;
        ListNode* last;
        first = head;
        last = head;
        int i = 0;
        while(first->next != nullptr)
        {
            i++;
            first = first->next;
            if(i == 2)
            {
                i = 0;
                last = last->next;
            }
        }
        if(i == 1)
            return last->next;
        return last;
    }
};

[now915]

1. 找到长度， 取中间值。2.双指针

var middleNode = function(head) {
    // if (!head.next) return head
    // let cur = head
    // let size = 0
    // while(cur) {
    //     cur = cur.next
    //     size++
    // }
    // cur = head
    // let mid = size % 2 ? Math.ceil(size / 2) : Math.ceil(size / 2) + 1
    // for(let i = 1; i < mid; i++) {
    //     cur = cur.next
    // }
    // return cur

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

• 空间复杂度 O(1)
• 时间复杂度 O(n)

[HWFrankFung]

Codes

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode quick=head,slow=head;
        while(quick.next!=null) {
            // quick 走两步
            quick = quick.next;
            if(quick.next!=null)
                quick = quick.next;
            // slow 走一步
            slow = slow.next;
        }
        return slow;
    }
}

[linyang4]

思路

双指针, 快指针每次走2步, 慢指针每次走1步, 等快指针走到链表尾部的时候, 慢指针正好走到链表的中间

代码

var middleNode = function(head) {
    let left = right = head
    while(right && right.next) {
        right = right.next.next
        left = left.next
    }
    return left
};

复杂度

• 时间复杂度: O(n)
• 空间复杂度: O(1)

[Serena9]

代码

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

复杂度分析

时间复杂度：O(N)

空间复杂度：O(1)

[machuangmr]

代码

class Solution {
    public ListNode middleNode(ListNode head) {
    // 快慢指针，快指针有两步，慢指针走一步，
    if(head == null || head.next == null) {
        return head;
    }
    ListNode fast = head, slow = head;
    while(fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    return slow;
    }
}

复杂度

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

[lonkang]

思路

双指针法 用两个指针记为快指针和慢指针, 快指针每次走 2 步，慢指针每次走 1 步，当快指针走到末尾的时候，慢指针刚好到达链表中点。

代码

var middleNode = function(head) {
    let step1 = head, step2 = head
    while(step2 && step2.next){
        step1 = step1.next
        step2 = step2.next.next
    }
    return step1
};

[phybrain]

思路

双指针

代码

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

复杂度分析

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

[stackvoid]

思路

双指针，比价简单。

代码

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

复杂度分析

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

[baddate]

题目

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

思路

快慢指针

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* slow;
        ListNode* fast;
        while(fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
};

复杂度分析

• 时间复杂度：O(N)，其中N是给定链表的结点数目。
• 空间复杂度：O(1)

[YuhanJYH]

思路： 遍历一遍，算出需要走几步

class Solution {
public:
    ListNode* middleNode(ListNode* head) 
    {
        if(!head)
        {
            return nullptr;
        }
        else if(!head->next)
        {
            return head;
        }

        ListNode* head_cpy{head};

        int length{0};

        while(head != nullptr)
        {
            head = head->next;
            length++;
        }

        int step{0};
        if(length%2)
        {
            step = (length-1)/2;
        }
        else
        {
            step = length/2;
        }

        while(step--)
        {
            head_cpy = head_cpy->next;
        }
        return head_cpy;
    }
};

time: O(n) space: O(1)

[CodeWithIris]

Question

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

Note (Fast and slow pointer)

• The fast pointer moves two steps while slow pointer moves one step at a time. When the fast pointer moves to the end of the linked list, the position of the slow pointer is the middle of the linked list.

Solution (C++)

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

Complexity

• T: O(n)
• S: O(1)