Question

328. Odd Even Linked List

中文文档

Description

Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return _the reordered list_.

The first node is considered odd, and the second node is even, and so on.

Note that the relative order inside both the even and odd groups should remain as it was in the input.

You must solve the problem in O(1) extra space complexity and O(n) time complexity.

 

Example 1:

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

Example 2:

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

 

Constraints:

• The number of nodes in the linked list is in the range [0, 104].
• -106 <= Node.val <= 106

Solutions

Solution 1: Single Pass

We can use two pointers $a$ and $b$ to represent the tail nodes of the odd and even nodes respectively. Initially, pointer $a$ points to the head node $head$ of the list, and pointer $b$ points to the second node $head.next$ of the list. In addition, we use a pointer $c$ to point to the head node $head.next$ of the even nodes, which is the initial position of pointer $b$.

We traverse the list, set pointer $a$ to point to the next node of $b$, i.e., $a.next = b.next$, then move pointer $a$ back by one position, i.e., $a = a.next$; set pointer $b$ to point to the next node of $a$, i.e., $b.next = a.next$, then move pointer $b$ back by one position, i.e., $b = b.next$. Continue to traverse until $b$ reaches the end of the list.

Finally, we set the tail node $a$ of the odd nodes to point to the head node $c$ of the even nodes, i.e., $a.next = c$, then return the head node $head$ of the list.

The time complexity is $O(n)$, where $n$ is the length of the list, and we need to traverse the list once. The space complexity is $O(1)$. We only need to maintain a limited number of pointers.

# Definition for singly-linked list.
# class ListNode:
#   def __init__(self, val=0, next=None):
#     self.val = val
#     self.next = next
class Solution:
  def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
    if head is None:
      return None
    a = head
    b = c = head.next
    while b and b.next:
      a.next = b.next
      a = a.next
      b.next = a.next
      b = b.next
    a.next = c
    return head

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *   int val;
 *   ListNode next;
 *   ListNode() {}
 *   ListNode(int val) { this.val = val; }
 *   ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
  public ListNode oddEvenList(ListNode head) {
    if (head == null) {
      return null;
    }
    ListNode a = head;
    ListNode b = head.next, c = b;
    while (b != null && b.next != null) {
      a.next = b.next;
      a = a.next;
      b.next = a.next;
      b = b.next;
    }
    a.next = c;
    return head;
  }
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *   int val;
 *   ListNode *next;
 *   ListNode() : val(0), next(nullptr) {}
 *   ListNode(int x) : val(x), next(nullptr) {}
 *   ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
  ListNode* oddEvenList(ListNode* head) {
    if (!head) {
      return nullptr;
    }
    ListNode* a = head;
    ListNode *b = head->next, *c = b;
    while (b && b->next) {
      a->next = b->next;
      a = a->next;
      b->next = a->next;
      b = b->next;
    }
    a->next = c;
    return head;
  }
};

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *   Val int
 *   Next *ListNode
 * }
 */
func oddEvenList(head *ListNode) *ListNode {
  if head == nil {
    return nil
  }
  a := head
  b, c := head.Next, head.Next
  for b != nil && b.Next != nil {
    a.Next = b.Next
    a = a.Next
    b.Next = a.Next
    b = b.Next
  }
  a.Next = c
  return head
}

/**
 * Definition for singly-linked list.
 * class ListNode {
 *   val: number
 *   next: ListNode | null
 *   constructor(val?: number, next?: ListNode | null) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 *   }
 * }
 */

function oddEvenList(head: ListNode | null): ListNode | null {
  if (!head) {
    return null;
  }
  let [a, b, c] = [head, head.next, head.next];
  while (b && b.next) {
    a.next = b.next;
    a = a.next;
    b.next = a.next;
    b = b.next;
  }
  a.next = c;
  return head;
}