package question;

public class Question328 {
 //示例 1:
 //
 //输入: 1->2->3->4->5->NULL
 // 1 3 2 4 5
 //输出: 1->3->5->2->4->NULL
 //示例 2:
 //
 //输入: 2->1->3->5->6->4->7->NULL
 //输出: 2->3->6->7->1->5->4->NULL
 public ListNode oddEvenList(ListNode head) {
 if (head==null||head.next==null||head.next.next==null) return head;
 ListNode p = head;
 ListNode q = head.next.next;

 while (q!=null) {
 ListNode t = p.next;
 ListNode qq = q.next;
 p.next=q;
 t.next=q.next;
 q.next=t;
 p=p.next;
 if (qq==null) break;
 q=qq.next;
 }
 return head;
 }

 public static void main(String[] args) {
 ListNode l1 = new ListNode(1);
 ListNode l2 = new ListNode(2);
 ListNode l3 = new ListNode(3);
 ListNode l4 = new ListNode(4);
 ListNode l5 = new ListNode(5);
 l1.next=l2;
 l2.next=l3;
 l3.next=l4;
 l4.next=l5;
 ListNode res = new Question328().oddEvenList(l1);
 while (res!=null) {
 System.out.println(res.val);
 res=res.next;
 }
 }
}