牛客在线编程101-14 链表的奇偶重排

旧城等待， 2023-10-04 19:39 18阅读 0赞

### 题目 ###

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

数据范围：节点数量满足 0 \\le n \\le 10^50≤n≤10  
5  
，节点中的值都满足 0 \\le val \\le 10000≤val≤1000  
要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)

### 解析 ###

把奇、偶数位置上的节点分别组成链表，把偶数节点放到奇数节点后面，因此只需要找到奇链表的最后一个元素和偶链表的第一个元素，组合成新链表

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) {
        
                return head;
            }
    
            int i = 1;
    
            //偶链表的头和指针
            ListNode p2 = null;
            ListNode p2_cur = null;
    
            ListNode cur = head;
            while(cur != null && cur.next != null) {
        
                if(i % 2 == 1) {
        
                    //当前节点为奇，下一个则为偶，把偶节点排列起来
                    if (p2 == null) {
        
                        p2 = cur.next;
                        p2_cur = p2;
                    } else {
        
                        p2_cur.next = cur.next;
                        p2_cur = cur.next;
                    }
                    //奇节点排列
                    if (cur.next.next != null) {
        
                        cur.next = cur.next.next;
                    } else {
        
                        break;
                    }
                }
                cur = cur.next;
                i++;
                i++;
            }
            //cur值就是奇节点的最后一个
            cur.next = p2;
            if(p2_cur != null) {
        
                p2_cur.next = null;
            }
    
            return head;
        }
    }