题目

描述

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

方法一

• 链表，数组；题目要求将奇数位的所有节点放在前面，偶数位的所有节点放在后面，且以位置下标进行升序排序。那么便可以先找出所有的偶数位节点以及奇数位节点，然后创建一个新的链表，奇数位节点放在前面，偶数位节点放在后面，返回新链表的头结点即可。
• 代码如下：

  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 p = head;
        // 奇数位列表
        List<Integer> odd = new ArrayList<>();
        // 偶数位列表
        List<Integer> even = new ArrayList<>();
        while(p != null){
            // 奇位数
            odd.add(p.val);
            p = p.next;
            if (p != null){
                // 偶位数
                even.add(p.val);
                p = p.next;
                continue;
            }
            break;
        }
        // 生成返回列表
        ListNode res = new ListNode(0);
        ListNode root = res;
        // 奇位数
        for(Integer i : odd){
            ListNode node = new ListNode(i);
            root.next = node;
            root =  node;
        }
        // 偶位数
        for (Integer i : even){
            ListNode node = new ListNode(i);
            root.next = node;
            root =  node;
        }
        return res.next;
    }
  }

• 时间复杂度：，遍历整个链表，长度为n；
• 空间复杂度：，生成了一个新的链表。

方法二

思路

• 双指针，链表；方法一需要创建一个新的链表，用到的空间复杂度，那么如何将空间复杂度降低为呢？
• 可以考虑使用双指针，分别为奇数位指针odd以及偶数位指针even，这里面有一个常识就是偶数位节点后就是奇数位，即even.next = odd；所以在循环时寻找奇数位，只需使odd = even.next；可以将奇数位的指针插在上一个奇数位节点之后，并将偶数位节点的头结点置于该节点之后，如此循环至链表尾部即可。
• 参考下图示例：
  
• 代码如下

  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) {
        if (head == null || head.next == null || head.next.next == null){
            return head;
        }
        // 链表头
        ListNode root = head;
        // 偶位节点指针
        ListNode even = root.next;
        // 偶位链表头指针
        ListNode evenHead = even;
        // 奇位节点指针
        ListNode odd = even.next;
        try{
            while(odd != null){
                ListNode temp = odd.next;
                // 将奇位节点移至前端
                root.next = odd;
                root = root.next;
                // 将奇位链表的末端与偶位链表的首端相接
                odd.next = evenHead;
                even.next = temp;
                even = even.next;
                // 找到下一个奇位节点
                odd = even.next;
            }
        }catch(Exception e){
            // 遍历到链表尾部，抛空异常
        }
        return head;
    }
  }

• 时间复杂度：，n/2次循环，所以是；
• 空间复杂度：，常数级空间复杂度。