【一次过】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;
    }
}