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

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
        if(head==null || head.next==null|| head.next.next==null){
            return head;
        }
        ListNode head2 = new ListNode(-1);
        ListNode p=head;
        ListNode rear=p;
        ListNode q=head2;
        while(p!=null){
            q.next=p.next;
            if(p.next!=null){
                p.next=p.next.next;
            }else{
                p.next=null;
            }
            q=q.next;
            rear=p;
            p=p.next;
        }
        rear.next=head2.next;
        return head;
    }
}

方法：双指针

解题思路：设立一个遍历原链表的指针作为奇数位链表 和 一个指代偶数位链表的指针，还要维护一个指向奇数节点的指针。从第一个结点开始遍历，每遍历一个结点都让新链表指针指向该结点的下一结点，然后奇链表的指针指向下下个结点，直到末尾，注意访问p.next.next;时先保证p.next存在。