[LeetCode Python 3] 876. Middle of the Linked List

ThinkSNS 發(fā)布于2019-07-30 17:23 / 477人閱讀

摘要：如果有兩個中間結(jié)點，則返回第二個中間結(jié)點。示例輸入輸出此列表中的結(jié)點序列化形式返回的結(jié)點值為。測評系統(tǒng)對該結(jié)點序列化表述是。提示給定鏈表的結(jié)點數(shù)介于和之間。

給定一個帶有頭結(jié)點 head 的非空單鏈表，返回鏈表的中間結(jié)點。

如果有兩個中間結(jié)點，則返回第二個中間結(jié)點。

示例 1：

輸入：[1,2,3,4,5]
輸出：此列表中的結(jié)點 3 (序列化形式：[3,4,5])
返回的結(jié)點值為 3 。 (測評系統(tǒng)對該結(jié)點序列化表述是 [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]
輸出：此列表中的結(jié)點 4 (序列化形式：[4,5,6])
由于該列表有兩個中間結(jié)點，值分別為 3 和 4，我們返回第二個結(jié)點。

提示：

給定鏈表的結(jié)點數(shù)介于 1 和 100 之間。

思路：

設(shè)置兩個指向頭節(jié)點的快慢指針，快指針每次走兩步，慢指針每次走一步，當(dāng)快指針到達最后結(jié)點或為空時，慢指針指向的就是中間結(jié)點。

解題代碼Python 3：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def middleNode(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        pa=pb=head
        while pa and pb.next:
            if pb.next.next==None:
                return pa.next
            pa=pa.next
            pb=pb.next.next
        return pa

云服務(wù)器 GPU云服務(wù)器 Middle linked the LeetCode

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/42196.html

相關(guān)文章

Leetcode PHP題解--D35 876. Middle of the Linked List

摘要：題目鏈接題目分析返回一個鏈表中最中間的元素。思路先全部塞入數(shù)組，再根據(jù)長度得到中間元素的下標(biāo)，再返回。最終代碼若覺得本文章對你有用，歡迎用愛發(fā)電資助。 876. Middle of the Linked List 題目鏈接 876. Middle of the Linked List 題目分析返回一個鏈表中最中間的元素。思路先全部塞入數(shù)組，再根據(jù)長度/2得到中間元素的下標(biāo)，再返回...

layman 2019-07-01 12:42 評論0 收藏0
LeetCode707：設(shè)計鏈表 Design Linked List

摘要：愛寫設(shè)計鏈表的實現(xiàn)。單鏈表中的節(jié)點應(yīng)該具有兩個屬性和。插入后，新節(jié)點將成為鏈表的第一個節(jié)點。將值為的節(jié)點追加到鏈表的最后一個元素。如果等于鏈表的長度，則該節(jié)點將附加到鏈表的末尾。如果索引有效，則刪除鏈表中的第個節(jié)點。操作次數(shù)將在之內(nèi)。愛寫bug (ID:iCodeBugs) 設(shè)計鏈表的實現(xiàn)。您可以選擇使用單鏈表或雙鏈表。單鏈表中的節(jié)點應(yīng)該具有兩個屬性：val 和 next。val 是...

iliyaku 2019-08-16 18:34 評論0 收藏0
LeetCode707：設(shè)計鏈表 Design Linked List

摘要：愛寫設(shè)計鏈表的實現(xiàn)。單鏈表中的節(jié)點應(yīng)該具有兩個屬性和。插入后，新節(jié)點將成為鏈表的第一個節(jié)點。將值為的節(jié)點追加到鏈表的最后一個元素。如果等于鏈表的長度，則該節(jié)點將附加到鏈表的末尾。如果索引有效，則刪除鏈表中的第個節(jié)點。操作次數(shù)將在之內(nèi)。愛寫bug (ID:iCodeBugs) 設(shè)計鏈表的實現(xiàn)。您可以選擇使用單鏈表或雙鏈表。單鏈表中的節(jié)點應(yīng)該具有兩個屬性：val 和 next。val 是...

FullStackDeveloper 2019-07-31 11:28 評論0 收藏0
LeetCode 160：相交鏈表 Intersection of Two Linked List

摘要：示例輸入輸出輸入解釋相交節(jié)點的值為注意，如果兩個列表相交則不能為。解釋這兩個鏈表不相交，因此返回。注意如果兩個鏈表沒有交點，返回在返回結(jié)果后，兩個鏈表仍須保持原有的結(jié)構(gòu)。此時將指向鏈表長鏈表的頭節(jié)點，不變。愛寫B(tài)ug（ID：iCodeBugs）編寫一個程序，找到兩個單鏈表相交的起始節(jié)點。 Write a program to find the node at which the i...

wing324 2019-08-16 18:38 評論0 收藏0
LeetCode 160：相交鏈表 Intersection of Two Linked List

摘要：示例輸入輸出輸入解釋相交節(jié)點的值為注意，如果兩個列表相交則不能為。解釋這兩個鏈表不相交，因此返回。注意如果兩個鏈表沒有交點，返回在返回結(jié)果后，兩個鏈表仍須保持原有的結(jié)構(gòu)。此時將指向鏈表長鏈表的頭節(jié)點，不變。愛寫B(tài)ug（ID：iCodeBugs）編寫一個程序，找到兩個單鏈表相交的起始節(jié)點。 Write a program to find the node at which the i...

ormsf 2019-07-31 11:29 評論0 收藏0