0%

链表逆置合集

206. 反转链表

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

示例 1:

img

输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]

示例 2:

img

输入:head = [1,2]
输出:[2,1]

示例 3:

输入:head = []
输出:[]

提示:

  • 链表中节点的数目范围是 [0, 5000]
  • -5000 <= Node.val <= 5000

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* reverseList(ListNode* head) {
if(!head) return nullptr;
if(!head -> next) return head;
ListNode* res = reverseList(head -> next);
head -> next -> next = head;
// 用例:1->2->3
// 返回3
// 3->2->null
// 3->2->1->null
head -> next = nullptr;
return res;
}
};

剑指 Offer 06. 从尾到头打印链表

输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。

示例 1:

输入:head = [1,3,2]
输出:[2,3,1]

C++

class Solution {
public:
vector<int> reversePrint(ListNode* head) {
if(!head) return {};
vector<int> res = reversePrint(head -> next);
res.push_back(head -> val);
return res;
}
};

92. 反转链表 II

给你单链表的头指针 head 和两个整数 leftright ,其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点,返回 反转后的链表

示例 1:

img

输入:head = [1,2,3,4,5], left = 2, right = 4
输出:[1,4,3,2,5]

示例 2:

输入:head = [5], left = 1, right = 1
输出:[5]

提示:

  • 链表中节点数目为 n
  • 1 <= n <= 500
  • -500 <= Node.val <= 500
  • 1 <= left <= right <= n

C++

image-20221107183715429

/**
* 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:
// 头插法, 每次将遍历到的节点插入到 left节点左侧
// 1-> 2 ->3->4->5 翻转2-4
// 1-> 3 ->2->4->5
// 1-> 4 ->3->2->5
ListNode* reverseBetween(ListNode* head, int left, int right) {
ListNode* dummyHead = new ListNode(0); // dummyHead 是为了让 pre 不为空
dummyHead -> next = head;
ListNode* pre = dummyHead;
ListNode* cur = head;
ListNode* nxt = cur -> next;

// 找到 left处的节点,即为cur, pre一直是left前不用换的那个节点, nxt是cur后的节点, cur和nxt会不停变换
for(int i = 1; i < left; i++){
pre = cur;
cur = cur -> next;
nxt = cur -> next;
}

// 每次把 nxt 头插进去
for(int i = left; i < right; i ++){
cur -> next = nxt -> next;
nxt -> next = pre -> next;
pre -> next = nxt;
nxt = cur -> next;
}
return dummyHead -> next;
}
};

24. 两两交换链表中的节点

给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。

示例 1:

img

输入:head = [1,2,3,4]
输出:[2,1,4,3]

示例 2:

输入:head = []
输出:[]

示例 3:

输入:head = [1]
输出:[1]

提示:

  • 链表中节点的数目在范围 [0, 100]
  • 0 <= Node.val <= 100

C++

/*
迭代:
创建哑结点 dummyHead,令 dummyHead.next = head。令 temp 表示当前到达的节点,初始时 temp = dummyHead。每次需要交换 temp 后面的两个节点。

如果 temp 的后面没有节点或者只有一个节点,则没有更多的节点需要交换,因此结束交换。否则,获得 temp 后面的两个节点 node1 和 node2,通过更新节点的指针关系实现两两交换节点。

具体而言,交换之前的节点关系是 temp -> node1 -> node2,交换之后的节点关系要变成 temp -> node2 -> node1,因此需要进行如下操作。

temp.next = node2
node1.next = node2.next
node2.next = node1

完成上述操作之后,节点关系即变成 temp -> node2 -> node1。再令 temp = node1,对链表中的其余节点进行两两交换,直到全部节点都被两两交换。

两两交换链表中的节点之后,新的链表的头节点是 dummyHead.next,返回新的链表的头节点即可。
*/

/**
* 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) return nullptr;
ListNode* dummyHead = new ListNode(0);
dummyHead -> next = head;
ListNode* temp = dummyHead;
while(temp -> next && temp -> next -> next){
ListNode* a = temp -> next;
ListNode* b = temp -> next -> next;
a -> next = b -> next;
b -> next = a;
temp -> next = b;
temp = a;
}
return dummyHead -> next;
}
};
  • 递归
image-20221105224311896
/**
* 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 || !head -> next) return head;
ListNode* a = head -> next;
ListNode* b = head -> next -> next;
head -> next -> next = head;
head -> next = swapPairs(b);
return a;
}
};

25. K 个一组翻转链表

给你链表的头节点 head ,每 k 个节点一组进行翻转,请你返回修改后的链表。

k 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。

示例 1:

img

输入:head = [1,2,3,4,5], k = 2
输出:[2,1,4,3,5]

示例 2:

img

输入:head = [1,2,3,4,5], k = 3
输出:[3,2,1,4,5]

提示:

  • 链表中的节点数目为 n
  • 1 <= k <= n <= 5000
  • 0 <= Node.val <= 1000

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* reverseKGroup(ListNode* head, int k) {
int len = 0;

ListNode* dummyHead = new ListNode(0);
dummyHead -> next = head;

ListNode* curr = head;
ListNode* prev = dummyHead;

while(head){
len ++;
head = head -> next;
}
head = dummyHead -> next;

for(int i = 0; i< len / k; i ++){
pair<ListNode*,ListNode*> p = reverse(curr, k);
prev -> next = p.first;
curr -> next = p.second;
prev = curr;
curr = curr -> next;
}

return dummyHead -> next;
}

pair<ListNode*,ListNode*> reverse(ListNode* head, int k){ //返回翻转后的 <新头节点,原来尾部下一个节点>
if(k == 1) return {head, head -> next};
pair<ListNode*,ListNode*> res = reverse(head -> next, --k);
head -> next -> next = head;
head -> next = nullptr;
return res;
}
};