328. 奇偶链表（中等）

小灰灰 2022-09-09 09:28 180阅读 0赞

Leetcode链接：[328. 奇偶链表][328.]

### 题目描述 ###

> 给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。  
>   
>   
> 请尝试使用原地算法完成。你的算法的`空间复杂度`应为 `O(1)`，`时间复杂度`应为 `O(nodes)`，nodes 为节点总数。

示例 1:

> 输入: 1->2->3->4->5->NULL  
> 输出: 1->3->5->2->4->NULL

示例 2:

> 输入: 2->1->3->5->6->4->7->NULL  
> 输出: 2->3->6->7->1->5->4->NULL

说明:

*  应当保持奇数节点和偶数节点的相对顺序。
 *  链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。

### 源码 ###

##### 方法一：分别存储奇偶链表，合并 #####

*  odd存放奇数节点链表
 *  even存放偶数节点链表

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        
        public ListNode oddEvenList(ListNode head) {
        
            if(head == null) return head;
    
            ListNode odd = new ListNode(0);
            ListNode even = new ListNode(0);
    
            ListNode currOdd = odd;
            ListNode currEven = even;
            ListNode curr = head;
    
            int count = 0;
            while(curr != null){
        
                if(count % 2 == 0){
        
                    currOdd.next = curr;
                    curr = curr.next;
                    currOdd = currOdd.next;
                }else if(count % 2 != 0){
        
                    currEven.next = curr;
                    curr = curr.next;
                    currEven = currEven.next;
                }
                count ++;
            }
    
    		//将链表尾部置空，防止存在换的现象
            currOdd.next = null;
            currEven.next = null;
    
            currOdd.next = even.next;
            return odd.next;
        }
    }

疑问：为什么要加以下两句代码？

//将链表尾部置空，防止存在换的现象
    currOdd.next = null;
    currEven.next = null;

###### 图解链表转移过程 ######

初始化奇偶链表头部  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5LqM6L-b5Yi25p2v6I6r5YGc_size_19_color_FFFFFF_t_70_g_se_x_16]

处理第1个节点

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5LqM6L-b5Yi25p2v6I6r5YGc_size_20_color_FFFFFF_t_70_g_se_x_16]

处理第2个节点  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5LqM6L-b5Yi25p2v6I6r5YGc_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
处理第3个节点  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5LqM6L-b5Yi25p2v6I6r5YGc_size_18_color_FFFFFF_t_70_g_se_x_16]

处理第4个节点

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5LqM6L-b5Yi25p2v6I6r5YGc_size_18_color_FFFFFF_t_70_g_se_x_16 1]  
处理第5个节点

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5LqM6L-b5Yi25p2v6I6r5YGc_size_19_color_FFFFFF_t_70_g_se_x_16 1]  
如果不将两个链表的末尾置空，在链接的时候，那么将`出现环`！

currOdd.next = even.next;

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5LqM6L-b5Yi25p2v6I6r5YGc_size_20_color_FFFFFF_t_70_g_se_x_16 2]

[328.]: https://leetcode-cn.com/problems/odd-even-linked-list/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5LqM6L-b5Yi25p2v6I6r5YGc_size_19_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/a6936e9dbf1649d894cdd733cfcc622e.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5LqM6L-b5Yi25p2v6I6r5YGc_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/388678c1930245a591be5d4034639b43.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5LqM6L-b5Yi25p2v6I6r5YGc_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/7caaa1b0affb416cb84d1f4c997189b2.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5LqM6L-b5Yi25p2v6I6r5YGc_size_18_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/c28209e0a7ea46db9960ed838f2c6c22.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5LqM6L-b5Yi25p2v6I6r5YGc_size_18_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/ef22e9bba10c43eab4180fa1f3f1a8ec.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5LqM6L-b5Yi25p2v6I6r5YGc_size_19_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/fdb9191d03cb4f2892086721de7adedb.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5LqM6L-b5Yi25p2v6I6r5YGc_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220829/66924c7cf9be4b4e829e0913b8e6b91f.png