给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
示例 1:
输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/odd-even-linked-list
1 public class OddEvenLinkedList { 2 static class ListNode { 3 int val; 4 ListNode next; 5 ListNode(int x) { 6 val = x; 7 } 8 } 9 public ListNode oddEvenList1(ListNode head) { 10 ListNode cur = head.next; 11 ListNode curOdd = head; 12 while(cur != null && cur.next !=null) { 13 ListNode odd = cur.next; //新的奇数位结点 14 ListNode next = cur.next.next; //下一个被操作的偶数位结点 15 ListNode even = curOdd.next; //当前奇数位后的偶数结点 16 cur.next = next; //当前偶数位结点指向下一个被操作的偶数位结点 17 curOdd.next = odd; //当前奇数位结点指向新的奇数位结点 18 odd.next = even; //新奇数位结点指向当前奇数位后的偶数结点 19 cur = next; //开始新的循环 20 curOdd = odd; 21 } 22 return head; 23 } 24 public ListNode oddEvenList2(ListNode head) { 25 if (head == null) { 26 return head; 27 } 28 ListNode odd = head; 29 ListNode even = head.next; 30 ListNode evenHead = even; //记录第一个偶数位结点 31 while (even != null && even.next != null) { 32 odd.next = odd.next.next; 33 odd = odd.next; 34 even.next = even.next.next; 35 even = even.next; 36 } 37 odd.next = evenHead; //奇数位结点最后一个结点指向记录的第一个偶数位结点，形成新的链表 38 return head; 39 } 40 41 }