链表的奇偶重排

 链表的奇偶重排_牛客题霸_牛客网 (nowcoder.com)

描述

给定一个单链表，请设定一个函数，将链表的奇数位节点和偶数位节点分别放在一起，重排后输出。

注意是节点的编号而非节点的数值。

数据范围：节点数量满足 0≤n≤1e5，节点中的值都满足 0≤ val ≤1000

要求：空间复杂度 O(n)，时间复杂度 O(n)

示例1

输入：{1,2,3,4,5,6}
返回值：{1,3,5,2,4,6}

说明：1->2->3->4->5->6->NULL

        重排后为

        1->3->5->2->4->6->NULL

示例2

输入：{1,4,6,3,7}

返回值：{1,6,7,4,3}

说明：

1->4->6->3->7->NULL

重排后为

1->6->7->4->3->NULL
奇数位节点有1,6,7，偶数位节点有4,3。重排后为1,6,7,4,3

备注：

链表长度不大于200000。每个数范围均在int内。

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode oddEvenList (ListNode head) {
        // write code here
        ListNode head1=new ListNode(0);
        ListNode head2=new ListNode(0);
        ListNode p=head;
        ListNode p1=head1;
        ListNode p2=head2;
        int i=0;
        while(p!=null){
            
                if(i%2==0) {
                    p1.next=new ListNode(p.val);
                                    p1=p1.next;
                }           
                else{
                    p2.next=new ListNode(p.val);
                p2=p2.next;
  
                }          
            p=p.next;
            i++;
        }
        
        p1.next=head2.next;
    return head1.next;

    }
    }