博文中会简要介绍Leetcode P0024题目分析及解题思路。
“Swap Nodes in Pairs”是一道比较经典的链表题目的简化版，其原型是“Swap Nodes in K Group”，即p0025。这道题主要考察的还是链表的插入、删除和结点交换等常规操作。
Given a linked list, swap every two adjacent nodes and return its head.
You may not modify the values in the list’s nodes, only nodes itself may be changed.
这道题的思路比较直接，时间复杂度是O(n)。
以下是Java的题解代码实现。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode dummy = new ListNode(0, head);
ListNode prev = dummy, curr = head;
while (curr != null && curr.next != null) {
prev.next = curr.next;
curr.next = curr.next.next;
prev.next.next = curr;
prev = curr;
curr = curr.next;
}
return dummy.next;
}
}
以下是C++的题解代码实现。
/**
* 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) {
if (head == NULL || head->next == NULL)
return head;
ListNode *dummy = new ListNode(0, head);
ListNode *prev = dummy, *curr = head;
while (curr != NULL && curr->next != NULL) {
prev->next = curr->next;
curr->next = curr->next->next;
prev->next->next = curr;
prev = curr;
curr = curr->next;
}
return dummy->next;
}
};