[数据结构与算法]BM14 链表的奇偶重排

题目

题目源自牛客
描述
给定一个单链表，请设定一个函数，将链表的奇数位节点和偶数位节点分别放在一起，重排后输出。注意是节点的编号而非节点的数值。

示例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内。

思路

根据题目，可以想办法找出奇数位链表和偶数位链表，然后奇数位链表的最后一个节点的next指向偶数位链表的头结点，就可以串起来了。
首先需要保存偶数位的头结点，即resDouble。在遍历链表时可以先不管while循环的执行条件，先写逻辑。

现在来看遍历条件，while中首先使用了singleNode和doubleNode的next，那么一定要保证singleNode和doubleNode不为空才能取其next，而doubleNode不为空则singleNode一定不为空，因为doubleNode是singleNode的next，因此先加上条件doubleNode != null。而条件doubleNode.next != null 是因为如果其为空了，则奇数链表由上图1移到3后，无法取也没必要再取3的next赋值给偶数位链表的下一个节点了。所以while条件是while(doubleNode != null && doubleNode.next != null)。

代码

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){
            return head;
        }
        ListNode resDouble = head.next;
        ListNode singleNode = head;
        ListNode doubleNode = head.next;
        while(doubleNode != null && doubleNode.next != null){
            singleNode.next = doubleNode.next;
            singleNode = singleNode.next;
            doubleNode.next = singleNode.next;
            doubleNode = doubleNode.next;
        }
        singleNode.next = resDouble;
        return head;
    }
}