题解 | #链表的奇偶重排#

、

/** * 13: 链表的奇偶重排 *给定一个单链表，请设定一个函数，将链表的奇数位节点和偶数位节点分别放在一起，重排后输出。 * 注意是节点的编号而非节点的数值。 * 解题思路：创建俩个额外的链表，分别用来存放奇数偶数，遍历完成后将俩个链表合并到一起 */

public ListNode oddEvenList (ListNode head) {
    if (head == null){
        return null;
    }
    if (head.next == null){
        return  head;
    }
    ListNode p=head;
    int n=1;//用来判断是奇数偶数
   ListNode Js=new ListNode(-1);//奇数链表
   ListNode Os=new ListNode(-1);//偶数链表
    ListNode cur = Js;
    ListNode cur1 = Os;
   while (p!=null){
       if (n%2!=0){//如果是奇数的话，用尾插法插到奇数链表后
           ListNode listNode = new ListNode(p.val);
           cur.next = listNode;
           cur=listNode;
       } else{//如果是偶数的话，用尾插法插到偶数链表后
           ListNode listNode = new ListNode(p.val);
           cur1.next = listNode;
           cur1=listNode;
       }
       p=p.next;
       n++;
   }
   p=Js;
   //将俩个链表合并
   while (p.next!=null){
       p=p.next;
   }
   p.next=Os.next;
   return Js.next;
}