143.md

Reorder List

Description

link

---

Solution

See Code

• 找到中间节点
• reverse第二部分
• 合并二者

---

Code

O(n)

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

class Solution:
    def reorderList(self, head):
        """
        :type head: ListNode
        :rtype: void Do not return anything, modify head in-place instead.
        """
        # find the middle of list
        # reverse the second half of list
        # insert one by one each element in 1st and 2nd halves.
        # runtime: 170ms
        if not head: 
            return head

        pi = pj = head
        
        while pj.next and pj.next.next: # j goes as twice as i.
            pi, pj = pi.next, pj.next.next
        
        cur = pi.next # start from 2nd half.
        node = pi.next = None
        while cur: # reverse 2nd half.
            next = cur.next
            cur.next = node
            node = cur
            cur = next
        
        cur1, cur2 = head, node
        while cur2: # insert 
            next1, next2 = cur1.next, cur2.next
            cur1.next, cur2.next = cur2, next1
            cur1, cur2 = next1, next2