LeetCode 0024 - Swap Nodes in Pairs
# Hints
- 链表 + 模拟
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Medium |
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.
Example:
Given 1->2->3->4, you should return the list as 2->1->4->3.
# 题意
给定一个链表,假想将链表中的节点从头到尾按每两个相邻节点一组划分,要求将每一组节点交换位置。如果最后存在单独一个节点则保持不变。
# 题解
按照题意模拟即可。本题的指针操作比较复杂,细节较多,建议写代码之前自己用纸笔画一下,很快就清楚了。
具体的指针操作过程如下:
初始时,令 指向靠前的待交换节点,令 表示 所指节点的前继节点。
令
prv->next = p->next
。令
p->next = p->next->next
。令
prv->next->next = p
。令 和 递进,循环执行操作。
下面给出操作过程的详细示例图:
当然,正确的过程并不是唯一的,这里给出的只是代码最简的过程。例如如果我们令 指向靠后的待交换节点,就可以简化思考的难度。
细节问题:
注意特判空链表。
注意处理链表长度为奇数的情况。
注意特殊处理头两个节点的指针操作。
# AC代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode * swapPairs(ListNode * head) {
// ����
if (head == nullptr || head->next == nullptr) {
return head;
}
// ����ͷ�ڵ�
ListNode * p = head;
head = p->next;
p->next = p->next->next;
head->next = p;
// ��ѭ��
ListNode * prv = p;
p = p->next;
while (p != nullptr && p->next != nullptr) {
// ����
prv->next = p->next;
p->next = p->next->next;
prv->next->next = p;
// �ݽ�
prv = p;
p = p->next;
}
// ����
return head;
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01