首页 > 代码库 > Leetcode:Swap Nodes in Pairs 链表成对交换节点

Leetcode:Swap Nodes in Pairs 链表成对交换节点

2024-07-08 00:12:51   216人阅读

Swap Nodes in Pairs：

Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

 

解题分析：

思路很简单，需要注意：

1. 链表第一个节点也可能被修改，存在 链表头节点操作和其余结点操作不统一的情况，我们虚拟一个前置结点指向链表的第一个节点

2. 防止断链，多用暂存结点

class Solution {
public:
    ListNode *swapPairs(ListNode *head) {
        if (head == nullptr) return nullptr;
        ListNode* newHead = new ListNode(0);
        newHead->next = head;
        
        ListNode* cur = newHead;
        while (cur != nullptr && cur->next != nullptr && cur->next->next != nullptr) {
            ListNode* first = cur->next;
            ListNode* second = cur->next->next;
            ListNode* nextNode = second->next;
            cur->next = second;
            cur->next->next = first;
            cur = cur->next->next;
            cur->next = nextNode; // 防止断链
        }
        return newHead->next;
    }
};

 


联系
我们