Algorithm


Problem Name: 143. Reorder List

You are given the head of a singly linked-list. The list can be represented as:

L0 → L1 → … → Ln - 1 → Ln

Reorder the list to be on the following form:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

You may not modify the values in the list's nodes. Only nodes themselves may be changed.

 

Example 1:

Input: head = [1,2,3,4]
Output: [1,4,2,3]

Example 2:

Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]

 

Constraints:

  • The number of nodes in the list is in the range [1, 5 * 104].
  • 1 <= Node.val <= 1000

 

Code Examples

#1 Code Example with C Programming

Code - C Programming


#include <stdio.h>
#include <stdlib.h>

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode *Helper(struct ListNode **forward, struct ListNode *node) {
    if (node == NULL || node->next == NULL) return node;

    struct ListNode *tail = Helper(forward, node->next);

    if (*forward == tail || (*forward)->next == tail) return tail;

    struct ListNode *t = (*forward)->next;
    (*forward)->next = tail;
    *forward = t;
    tail->next = t;

    return node;
}

void reorderList(struct ListNode* head) {
    if (head == NULL) return;
    struct ListNode *p = head;
    struct ListNode *mid = Helper(&p, head);
    mid->next = NULL;
}

struct ListNode *createNode(int new_data) {
    struct ListNode *new_node = (struct ListNode *)malloc(sizeof(struct ListNode));
    new_node->val = new_data;
    new_node->next = NULL;
    return new_node;
}

int main(){
    /* test 1 */
    struct ListNode *l1 = createNode(1);
    struct ListNode *p = l1;
    int i;
    for (i = 2; i  < = 5; i++) {
        p->next = createNode(i);
        p = p->next;
    }
    p->next = NULL;

    printf("List  1: ");
    p = l1;
    while (p) {
        printf("%d->", p->val);
        p = p->next;
    }
    printf("NIL\n");

    reorderList(l1);

    printf("Reorder: ");
    p = l1;
    while (p) {
        printf("%d->", p->val);
        p = p->next;
    }
    printf("NIL\n");

    /* test 2 */
    struct ListNode *l2 = createNode(1);
    p = l2;
    for (i = 2; i  < = 6; i++) {
        p->next = createNode(i);
        p = p->next;
    }
    p->next = NULL;

    printf("List  2: ");
    p = l2;
    while (p) {
        printf("%d->", p->val);
        p = p->next;
    }
    printf("NIL\n");

    reorderList(l2);

    printf("Reorder: ");
    p = l2;
    while (p) {
        printf("%d->", p->val);
        p = p->next;
    }
    printf("NIL\n");

    return 0;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
head = [1,2,3,4]

Output

x
+
cmd
[1,4,2,3]

#2 Code Example with Java Programming

Code - Java Programming


class Solution {
  public void reorderList(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
      slow = slow.next;
      fast = fast.next.next;
    }
    ListNode secondHalf = reverse(slow.next);
    slow.next = null;
    ListNode firstHalf = head;
    while (firstHalf != null && secondHalf != null) {
      ListNode firstHalfNext = firstHalf.next;
      ListNode secondHalfNext = secondHalf.next;
      firstHalf.next = secondHalf;
      secondHalf.next = firstHalfNext;
      firstHalf = firstHalfNext;
      secondHalf = secondHalfNext;
    }
  }
  
  private ListNode reverse(ListNode node) {
    ListNode curr = node;
    ListNode prev = null;
    while (curr != null) {
      ListNode next = curr.next;
      curr.next = prev;
      prev = curr;
      curr = next;
    }
    return prev;
  }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
head = [1,2,3,4]

Output

x
+
cmd
[1,4,2,3]

#3 Code Example with Javascript Programming

Code - Javascript Programming


const reorderList = function(head) {
  if(head == null) return head
  let slow = head, fast = head
  while(fast && fast.next) {
    slow = slow.next
    fast = fast.next.next
  }
  let head2 = reverse(slow.next)
  slow.next = null
  
  while(head && head2) {
    const next = head.next, next2 = head2.next
    head2.next = head.next
    head.next = head2
    head = next
    head2 = next2
  }
  
  function reverse(node) {
    let pre = null, cur = node
    while(cur) {
      const tmp = cur.next
      cur.next = pre
      pre = cur
      cur = tmp
    }
    return pre
  }
};
Copy The Code & Try With Live Editor

Input

x
+
cmd
head = [1,2,3,4,5]

Output

x
+
cmd
[1,5,2,4,3]

#4 Code Example with Python Programming

Code - Python Programming


class Solution(object):
    def reorderList(self, head):
        if head:
            arr = []
            while head:
                arr += head,
                head = head.next
            l, r, prev = 0, len(arr) - 1, ListNode(0)
            while l < r: prev.next, arr[l].next, prev, l, r = arr[l], arr[r], arr[r], l + 1, r - 1
            if l == r: prev.next = arr[l]
            arr[l].next = None
Copy The Code & Try With Live Editor

Input

x
+
cmd
head = [1,2,3,4,5]

Output

x
+
cmd
[1,5,2,4,3]

#5 Code Example with C# Programming

Code - C# Programming


namespace LeetCode
{
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     public int val;
     *     public ListNode next;
     *     public ListNode(int val=0, ListNode next=null) {
     *         this.val = val;
     *         this.next = next;
     *     }
     * }
     */
    public class _0143_ReorderList
    {
        public void ReorderList(ListNode head)
        {
            if (head == null) return;

            ListNode slow = head, fast = head;
            while (fast != null && fast.next != null)
            {
                slow = slow.next;
                fast = fast.next.next;
            }

            ListNode prev = null, curr = slow, temp;
            while (curr != null)
            {
                temp = curr.next;
                curr.next = prev;
                prev = curr;
                curr = temp;
            }

            ListNode first = head, second = prev;
            while (second.next != null)
            {
                temp = first.next;
                first.next = second;
                first = temp;

                temp = second.next;
                second.next = first;
                second = temp;
            }
        }
    }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
head = [1,2,3,4]

Output

x
+
cmd
[1,4,2,3]
Advertisements

Demonstration


Previous
#142 Leetcode Linked List Cycle II Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#144 Leetcode Binary Tree Preorder Traversal Solution in C, C++, Java, JavaScript, Python, C# Leetcode