登录
  • #刷题
  • #leetcode

Le‌‌‍‍‌‍‍‌‍‍‌‍‍‌‍‍‌‌‌‌‌‍‍‍‍‌‌‌‍‍‌‍etcode笔记 #328. Odd Even Linked List || Visualization

liuzz10
556
0
Leetcode #328. Odd Even Linked List



Problem

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

Example 1:

Input: 1->2->3->4->5->NULL

Output: 1->3->5->2->4->NULL

Idea: 2 pointers

We use 2 pointers:



  • A pointer `odd` to always track odd nodes and link odd nodes to the odd list.

  • A pointer `even` to alwasy track even nodes and link even nodes to the odd list.



Finally, we link even list after odd list.

The following graph describe the algorithm:









Code

[mw_shl_code=java,true]class Solution {

public ListNode oddEvenList(ListNode head) {

if (head == null) return null;

ListNode odd = head;

ListNode even = head.next;

ListNode evenHead = head.next;

// `even != null` rules out the list of only 1 node

// `even.next != null` rules out the list of only 2 nodes

while (even != null && even.next != null) {

// Put odd to the odd list

odd.next = odd.next.next;



// Put even to the even list

even.next = even.next.next;



// Move the pointer to the next odd/even

odd = odd.next;

even = even.next;

}

odd.next = evenHead;

return head;

}

}[/mw_shl_code]
0条回复
热度排序

发表回复