LC #143 Reorder List

less than 1 minute read

Method 1. Conversion to listPermalink

	# Definition for singly-linked list.
	# class ListNode:
	# def __init__(self, val=0, next=None):
	# self.val = val
	# self.next = next
	class Solution:
	def reorderList(self, head: ListNode) -> None:
	"""
	Do not return anything, modify head in-place instead.
	"""
	if head is None: return None


	nums = []
	curr = head
	while curr:
	nums.append(curr.val)
	curr = curr.next

	N = len(nums)
	nums2 = []
	for i in range(N//2):
	nums2.append(nums[i])
	nums2.append(nums[N-1-i])

	if N%2 == 1:
	nums2.append(nums[N//2])

	print(nums2)

	head.val = nums2[0]
	curr = head
	for n in nums2[1:]:
	curr.next = ListNode(n)
	curr = curr.next

view raw LC143mth1.py hosted with ❤ by GitHub

	# Definition for singly-linked list.
	# class ListNode:
	# def __init__(self, val=0, next=None):
	# self.val = val
	# self.next = next
	class Solution:
	def reorderList(self, head: ListNode) -> None:
	"""
	Do not return anything, modify head in-place instead.
	"""
	prev = None
	slow = head
	fast = head

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

	prev.next = None

	curr = head
	while curr:
	print(curr.val, end=", ")
	curr = curr.next

	print(" ")


	h0 = None
	h1 = slow
	next = None

	while h1:
	next = h1.next
	h1.next = h0
	h0 = h1
	h1 = next


	curr = h0
	while curr:
	print(curr.val, end=", ")
	curr = curr.next

	print(" ")
	h1 = head.next
	h2 = h0
	curr = head
	cnt = 0
	while h1 and h2:
	if cnt&1:
	curr.next = h1
	h1 = h1.next
	else:
	curr.next = h2
	h2 = h2.next
	cnt +=1
	curr = curr.next

	curr.next = h1 or h2

	return head

view raw LC143mth2.py hosted with ❤ by GitHub