【一次過】Lintcode 1292. 奇偶連結清單

給定單連結清單，将所有奇數節點連接配接在一起，然後将偶數節點連接配接在一起。 請注意，這裡我們讨論的是節點編号，而不是節點中的值。

樣例

樣例1:

輸入： 1->2->3->4->5->NULL
輸出： 1->3->5->2->4->NULL
           

樣例2:

輸入： 2->1->null
輸出： 2->1->null
           

注意事項

奇數節點和偶數節點的相對位置應當不變。

第一個節點應為奇數，第二個節點為偶數，以此類推……

解題思路：

    建立兩個連結清單分别存儲奇數索引的值與偶數索引的值，最後将兩個連結清單連接配接起來即可。

/**
 * Definition for ListNode
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param head: a singly linked list
     * @return: Modified linked list
     */
    public ListNode oddEvenList(ListNode head) {
        // write your code here
        ListNode odd = new ListNode(0);
        ListNode oddCur = odd;
        ListNode even = new ListNode(0);
        ListNode evenCur = even;
        
        int index = 1;
        while(head != null){
            if(index % 2 == 1){
                oddCur.next = head;
                oddCur = oddCur.next;
            }else{
                evenCur.next = head;
                evenCur = evenCur.next;
            }
            
            index++;
            head = head.next;
        }
        
        evenCur.next = null;
        oddCur.next = even.next;
        
        return odd.next;
    }
}