【题解】链表的奇偶重排_链表的奇偶重排python

链表的奇偶重排

题目链接：链表的奇偶重排

解题思路1：利用数组

利用数组的下标来定位奇偶位节点
先遍历链表，将链表节点值放入数组中
再根据下标控制奇偶，重新构造链表

代码如下：

    ListNode* oddEvenList(ListNode* head) {
        ListNode* cur = head;
        ListNode* res = new ListNode(-1);
        ListNode* pres = res;
        vector<int> v;
        while (cur != nullptr) {
            v.push_back(cur->val);
            cur = cur->next;
        }
        for (int i = 0; i < v.size();) {
            ListNode* p = new ListNode(v[i]);
            pres->next = p;
            pres = pres->next;
            i+=2;
        }
        for (int i = 1; i < v.size();) {
            ListNode* p = new ListNode(v[i]);
            pres->next = p;
            pres = pres->next;
            i+=2;
        }
        return res->next;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

解题思路2：双指针

首先判断空链表的情况，如果链表为空，直接返回
其次使用双指针fast和old分别遍历奇数节点和偶数节点，并给偶数节点一个表头，方便后面奇数节点和偶数节点的连接
每次遍历两个节点，跨越奇数或偶数节点找到想要连接的下一个节点
将偶数节点头连接在奇数节点后，再返回头部

代码如下：

    ListNode* oddEvenList(ListNode* head) {
        if(head == nullptr) return head;
        ListNode* fast = head->next;
        ListNode* old = head;
        ListNode* pfast = fast;
        while(fast!=nullptr && fast->next!=nullptr){
            old->next = fast->next;
            old = old->next;
            fast->next = old->next;
            fast = fast->next;
        }
        old->next = pfast;
        return head;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14