34-交换链表中的节点

自己的做法

算法思想

这题贼简单。

要交换正数第k个节点和倒数第k个节点的值。

只要找到这俩节点即可。

正数第k个节点很好找，只要从头节点向后走k - 1步即可。

找倒数第k个节点，可参考 链表中倒数第k个节点那道题。

使用快慢指针法。两个指针，former和rear，初始都指向头节点，rear向后走k步，然后两个指针同时向后走，当rear为空时，former指向的就是倒数第k个节点。

然后交换值即可。

算法实现

class Solution {
public:
    ListNode* swapNodes(ListNode* head, int k) {
        if(head == nullptr || head->next == nullptr) {
            return head;
        }

        ListNode * node = head;
        for(int i = 1; i <= k - 1; i++) {
            node = node->next;
        }
        ListNode * former = node;
        ListNode * rear = head;
        node = node->next;
        while (node) {
            node = node->next;
            rear = rear->next;
        }
        int temp = former->val;
        former->val = rear->val;
        rear->val = temp;
        return head;
    }
};

性能分析

时间复杂度：$O(n)$。

空间复杂度：$O(1)$。

无参考做法。