BM14. [链表的奇偶重排]

https://www.nowcoder.com/exam/oj?tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295

BM14. 链表的奇偶重排

https://www.nowcoder.com/practice/02bf49ea45cd486daa031614f9bd6fc3?tpId=295&sfm=github&channel=nowcoder

题目分析

既然有奇数和偶数那么直接取余数就可以判断是奇数节点还是偶数节点，此外这道题目主要考察的就是你的对链表操作的细节，还需要注意的就是，最后的偶链表的next必须赋值为null，因为不赋值为null，当你的链表是奇数总数的时候可能会返回一个含有环的链表。
图片示意

解法分析

定义奇节点，奇节点的伪节点，偶节点，偶节点的伪节点

int index = 1;
ListNode p1 = new ListNode(-1);
ListNode dummy1 = p1;
ListNode p2 = new ListNode(-1);
ListNode dummy2 = p2;

奇偶遍历同时记录奇数的pre节点

        while(head != null){
            //分别挂载在不同的链表上即可
            if(index % 2 == 1){
                p1.next = head;
                p1 = p1.next;
            }else{
                p2.next = head;
                p2 = p2.next;
            }
            index++;
            head = head.next;
        }

偶链表的next节点赋值null，奇链表的末尾链接偶链表的头

p2.next = null;
if(p1 != null){
    p1.next = dummy2.next;

完整题解

  public ListNode oddEvenList (ListNode head) {
       int index = 1;
       ListNode p1 = new ListNode(-1);
       ListNode dummy1 = p1;
       ListNode p2 = new ListNode(-1);
       ListNode dummy2 = p2;
       while(head != null){
           //分别挂载在不同的链表上即可
           if(index % 2 == 1){
               p1.next = head;
               p1 = p1.next;
           }else{
               p2.next = head;
               p2 = p2.next;
           }
           index++;
           head = head.next;
       }
       //没有这个可能就会成为一个环
       p2.next = null;
       if(p1 != null)
           p1.next = dummy2.next;
       return dummy1.next;
    }

复杂度分析

• 时间复杂度：，为链表的长度
• 空间复杂度：，没有使用新的额外空间