题目描述

思路

我想起了一位故人。。
前面那道分隔链表的题，只需要把<x的条件改为位置的奇偶即可完全照搬过来，出题人偷懒了属于是。
试着不抄代码重新写一遍：
简单写了一下发现这道题不太适合用递归算法求解，因为结点在整个链表中的位置不太好确认，试着用双指针法写一下：

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if(head == nullptr || head -> next == nullptr){
            return head;
        }
        if(head -> next -> next == nullptr){
            return head;
        }
        ListNode* Dummy = new ListNode(0, head);
        int location = 1;
        ListNode* slow = head;
        ListNode* fast = Dummy;

        while(fast -> next != nullptr){
            if(location%2 && location != 1){
            //奇数的情况,且位置为1的地方不需要处理
                ListNode* tmp = fast -> next ;
                fast -> next = fast -> next -> next;
                tmp -> next = slow -> next;
                slow -> next = tmp;
                slow = slow -> next;
				
                location++;
                continue;
		//因为提一个结点到前面去之后，fast->next已经自动指向
		//下一个节点了，这时如果再移动fast就会漏掉一个结点
            }
        location++;
        fast = fast -> next;
        }
        return head;
    }
};

本题与前面那个分隔链表相比的难点在于，将一个奇数结点提到前面以后，本来设置的节点位置有可能会紊乱从而导致错过某个结点。