LeetCode 143 Reorder List

LeetCode 143 Reorder List Problem

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

class Solution(object):
    # def reorderList(self, head):
    #     """
    #     :type head: ListNode
    #     :rtype: void Do not return anything, modify head in-place instead.
    #     """
    #     # List as index to rebuild relation
    #     if not head:
    #         return
    #     dmap = []
    #     current = head
    #     while current is not None:
    #         dmap.append(current)
    #         current = current.next
    #     ls = len(dmap)
    #     for i in range(ls / 2):
    #         t = -1 * (i + 1)
    #         dmap[t].next = dmap[i].next
    #         dmap[i].next = dmap[t]
    #     dmap[ls / 2].next = None

    def reorderList(self, head):
        # Two points
        if head is None or head.next is None:
            return
        p1, p2 = head, head.next
        while p2 and p2.next:
            p1 = p1.next
            p2 = p2.next.next
        head2 = p1.next
        p1.next = None
        p2 = head2.next
        head2.next = None
        # reverse mid->end to end->mid
        while p2:
            temp = p2.next
            p2.next = head2
            head2 = p2
            p2 = temp
        p1, p2 = head, head2
        # merge
        while p1:
            temp = p1.next
            p1.next = p2
            p1 = p1.next
            p2 = temp

Download Reorder List.py

List of all Reorder List problems

Leetcode 143 Reorder List problem solution in python3 with explanation. This is the best place to expand your knowledge and get prepared for your next interview.

Feedback is the most important part of any website.

If you have any query, suggestion or feedback, Please feel free to contact us.