链表：基本操作

0024. 两两交换链表中的节点 (opens new window)

题目

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

解析

使用两个辅助指针 pre 和 cur，每次交换 cur 和 cur->next 两个结点，交换终止条件为 pre 后面不存在两个未交换结点。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode *dummy = new ListNode(0);
        dummy->next = head;

        // 0 -> 1 -> 2 -> 3
        // pre  cur  next
        ListNode *pre = dummy, *cur = dummy->next;
        while (cur && cur->next) {
            ListNode *next = cur->next;
            pre->next = next;
            cur->next = next->next;
            next->next = cur;
            pre = cur;
            cur = cur->next;
        }

        return dummy->next;
    }
};

0061. 旋转链表 (opens new window)

题目

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

解析

将链表头尾相连形成一个环，根据链表总长度计算要旋转移动的长度，最后再将链表头尾断开即可。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (!head) return nullptr;

        // 尾结点指向头结点
        ListNode *cur = head;
        int n = 1;
        while (cur->next) cur = cur->next, n++;
        cur->next = head;

        // 找到分段点
        for (int i = 0; i < n - k % n; i++) {
            cur = cur->next;
        }

        // 从分段点切开
        head = cur->next;
        cur->next = nullptr;

        return head;
    }
};

0086. 分隔链表 (opens new window)

题目

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你应当 保留 两个分区中每个节点的初始相对位置。

解析

使用两个指针，分别维护小于 x 和大于等于 x 的两个链表，遍历原链表后将得到的两链表拼接即可。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode *lh = new ListNode(0), *l = lh;
        ListNode *rh = new ListNode(0), *r = rh;

        for (ListNode *cur = head; cur; cur = cur->next) {
            if (cur->val < x) l = l->next = cur;
            else r = r->next = cur;
        }
        l->next = rh->next;
        r->next = nullptr;

        return lh->next;
    }
};

0328. 奇偶链表 (opens new window)

题目

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。

解析

将原链表拆分成奇数节点链表和偶数节点链表，之后再将两个链表进行连接即可。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        ListNode* oddHead = new ListNode(0);
        ListNode* oddTail = oddHead;
        ListNode* evenHead = new ListNode(0);
        ListNode* evenTail = evenHead;

        ListNode* cur = head;

        bool isOdd = true;
        while (cur) {
            if (isOdd) {
                oddTail->next = cur;
                oddTail = oddTail->next;
            } else {
                evenTail->next = cur;
                evenTail = evenTail->next;
            }
            cur = cur->next;
            isOdd = !isOdd;
        }
        oddTail->next = evenHead->next;
        evenTail->next = NULL;

        return oddHead->next;
    }
};