【2024考研】题解11 | #链表的奇偶重排#

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* oddEvenList(ListNode* head) {
        // write code here
        //特例存在一方空表或者单位表，直接输出
        if(head == NULL || head->next == NULL){
            return head;
        }
        //奇偶数节点表头
        ListNode *oddhead = head;
        ListNode *oddtail = oddhead;
        //奇偶数节点表尾
        ListNode *evenhead = head->next;
        ListNode *eventail = evenhead;
        //以偶数为基准,双跨连接,奇动偶再动
        while (eventail != NULL && eventail->next != NULL) {
            oddtail->next = eventail->next;
            oddtail = oddtail->next;

            eventail->next = oddtail->next;
            eventail = oddtail->next;
        }
       
        //最后奇数节点尾连上偶数节点头
        oddtail->next = evenhead;
        //输出奇数在前
        return oddhead;
    }
};

基本算法思想

①该算法首先判断链表是否为空或只有一个节点，

②如果是，则直接返回原链表。然后创建两个指针oddHead和evenHead，分别指向奇数位节点的头节点和偶数位节点的头节点。

同时创建两个指针oddTail和evenTail，分别指向奇数位节点和偶数位节点的尾节点。

③然后使用一个循环，将奇数位节点和偶数位节点分别连接起来，直到遍历完整个链表。

④最后将奇数位节点的尾节点指向偶数位节点的头节点，并返回奇数位节点的头节点。

时空复杂度

该算法的时间复杂度为O(n)，其中n是链表的长度。算法遍历了整个链表一次。

空间复杂度为O(1)，只使用了常数级别的额外空间。