链表
两两交换链表中的节点
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1：
1
2
| 输入：head = [1,2,3,4]
输出：[2,1,4,3]
|
示例 2：
示例 3：
提示：
链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100
思路
定义一个虚拟头结点dummylisty，如果存在可以交换的节点，则按照题目要求把相应位置的节点插入到相应位置。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode *dummyList =new ListNode(-1,head);
dummyList->next = head;
if(dummyList->next == nullptr)
return nullptr;
if(head->next == nullptr)
return head;
ListNode *top = dummyList;
while(top->next!= nullptr && top->next->next != nullptr)
{
ListNode* tmp = top->next;
ListNode* tmp1 = top->next->next->next;
top->next = top->next->next;
top->next->next = tmp;
top->next->next->next = tmp1;
top = top->next->next;
}
return dummyList->next;
}
};
|
合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
1
2
| 输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* retList = new ListNode(0);
ListNode* dummy = retList;
while(l1 != nullptr && l2 != nullptr) {
if(l1->val < l2->val) {
dummy->next = l1;
l1 = l1->next;
} else {
dummy->next = l2;
l2 = l2->next;
}
dummy = dummy->next;
}
dummy->next = l1 == NULL ? l2 : l1;
return retList->next;
}
};
|
反转链表
题目描述
输入一个链表，反转链表后，输出新链表的表头。
示例1
输入
返回值
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution {
public:
ListNode* ReverseList(ListNode* pHead) {
ListNode *pre = nullptr;
ListNode *cur = pHead;
ListNode *nex = nullptr;
while(cur) {
nex = cur->next;
cur->next = pre;
pre = cur;
cur = nex;
}
return pre;
}
};
|
奇偶链表
给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
示例：
1
2
| >输入: 1->2->3->4->5->NULL
>输出: 1->3->5->2->4->NULL
|
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
ListNode* oddEvenList(ListNode* head) {
if (head == NULL)
return head;
ListNode* evenHead = head->next;
ListNode* odd = head;
ListNode* even = evenHead;
while(even != nullptr && even->next != nullptr) {
odd->next = even->next;
odd = odd->next;
even->next = odd->next;
even = even->next;
}
odd->next = evenHead;
return head;
}
};
|
复杂度分析
时间复杂度：O(n)O(n)，其中 nn 是链表的节点数。需要遍历链表中的每个节点，并更新指针。
空间复杂度：O(1)O(1)。只需要维护有限的指针。
