Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
leetcode-ll
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
"""
PC:
what if length of Linked List is even, there's two middle one. Is okay to just return the second one
Thought Process:
Using Array
Step1:Turn Linked list into Array
Step2:Get the middle node using index A[l//2]
Using slow and fast pointer
1->2->3
s
f
s
f
1->2->3->4
s
f
s
f
s
f
"""
def middleNode(self, head: ListNode) -> ListNode:
"""
T:O(n)
S:O(n)
"""
A = []
m = head
while m:
A.append(m)
m = m.next
return A[len(A)//2]
def middleNode(self, head: ListNode) -> ListNode:
"""
T:O(n)
S:O(1)
"""
s = f = head
while f and f.next:
s = s.next
f = f.next.next
return s
def middleNode(self, head: ListNode) -> ListNode:
cur = head
length = 0
nums = []
while cur:
nums.append(cur)
length += 1
cur = cur.next
return nums[length // 2]
def middleNode(self, head: ListNode) -> ListNode:
return self.get_middle_nod(head)
def get_middle_nod(self, head):
s = f = head
while f and f.next:
s = s.next
f = f.next.next
return s
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment