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

题目主要信息:

• 给定一个链表，将奇数位的节点依次连在前半部分，偶数位的节点依次连在后半部分
• 返回连接后的链表头

举一反三：

学习完本题的思路你可以解决如下题目：

BM4.合并有序链表

BM5.合并k个已排序的链表

BM6.判断链表中是否有环

BM7.链表中环的入口节点

BM8.链表中倒数最后k个节点

BM9.删除链表的倒数第n个节点

BM10.两个链表的第一个公共节点

BM13.判断一个链表是否为回文结构

方法：双指针（推荐使用）

知识点：双指针

双指针指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个指针（特殊情况甚至可以多个），两个指针或是同方向访问两个链表、或是同方向访问一个链表（快慢指针）、或是相反方向扫描（对撞指针），从而达到我们需要的目的。

思路：

如下图所示，第一个节点是奇数位，第二个节点是偶数，第二个节点后又是奇数位，因此可以断掉节点1和节点2之间的连接，指向节点2的后面即节点3，如红色箭头。如果此时我们将第一个节点指向第三个节点，就可以得到那么第三个节点后为偶数节点，因此我们又可以断掉节点2到节点3之间的连接，指向节点3后一个节点即节点4，如蓝色箭头。那么我们再将第二个节点指向第四个节点，又回到刚刚到情况了。

//odd连接even的后一个，即奇数位
odd.next = even.next; 
//odd进入后一个奇数位
odd = odd.next; 
//even连接后一个奇数的后一位，即偶数位
even.next = odd.next; 
//even进入后一个偶数位
even = even.next; 

这样我们就可以使用了两个同方向访问指针遍历解决这道题。

具体做法：

• step 1：判断空链表的情况，如果链表为空，不用重排。
• step 2：使用双指针odd和even分别遍历奇数节点和偶数节点，并给偶数节点链表一个头。
• step 3：上述过程，每次遍历两个节点，且even在后面，因此每轮循环用even检查后两个元素是否为NULL，如果不为再进入循环进行上述连接过程。
• step 4：将偶数节点头接在奇数最后一个节点后，再返回头部。

图示：

Java实现代码：

import java.util.*;
public class Solution {
    public ListNode oddEvenList (ListNode head) {
        //如果链表为空，不用重排
        if(head == null) 
            return head;
        //even开头指向第二个节点，可能为空
        ListNode even = head.next; 
        //odd开头指向第一个节点
        ListNode odd = head; 
        //指向even开头
        ListNode evenhead = even; 
        while(even != null && even.next != null){
            //odd连接even的后一个，即奇数位
            odd.next = even.next; 
            //odd进入后一个奇数位
            odd = odd.next; 
            //even连接后一个奇数的后一位，即偶数位
            even.next = odd.next; 
            //even进入后一个偶数位
            even = even.next; 
        } 
        //even整体接在odd后面
        odd.next = evenhead; 
        return head;
    }
}

C++实现代码：

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        //如果链表为空，不用重排
        if(head == NULL) 
            return head;
        //even开头指向第二个节点，可能为空
        ListNode* even = head->next; 
        //odd开头指向第一个节点
        ListNode* odd = head; 
        //指向even开头
        ListNode* evenhead = even; 
        while(even != NULL && even->next != NULL){ 
            //odd连接even的后一个，即奇数位
            odd->next = even->next; 
            //odd进入后一个奇数位
            odd = odd->next; 
            //even连接后一个奇数的后一位，即偶数位
            even->next = odd->next; 
            //even进入后一个偶数位
            even = even->next; 
        } 
        //even整体接在odd后面
        odd->next = evenhead; 
        return head;
    }
};

Python实现代码：

class Solution:
    def oddEvenList(self , head: ListNode) -> ListNode:
         #如果链表为空，不用重排
        if head == None:
            return head
        #even开头指向第二个节点，可能为空
        even = head.next 
        #odd开头指向第一个节点
        odd = head 
        #指向even开头
        evenhead = even 
        while even and even.next:
            #odd连接even的后一个，即奇数位
            odd.next = even.next 
            #odd进入后一个奇数位
            odd = odd.next 
            #even连接后一个奇数的后一位，即偶数位
            even.next = odd.next 
            #even进入后一个偶数位
            even = even.next 
        #even整体接在odd后面
        odd.next = evenhead 
        return head

复杂度分析：

• 时间复杂度：$O(n)O(n)$，遍历一次链表的所有节点
• 空间复杂度：$O(1)O(1)$，常数级指针，无额外辅助空间