1.合并两个排序的链表：迭代
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy=new ListNode(0); // 弄一个头节点
ListNode r=dummy; // 记录头节点，最后返回的时候使用
while(l1!=null&&l2!=null){
if(l1.val<=l2.val){
r.next=l1;
l1=l1.next;
} else{
r.next=l2;
l2=l2.next;
}
r=r.next;
}
r.next=l1==null?l2:l1;
return dummy.next;
}
2.反转链表：递归
直接用递归方法，不然很麻烦；递归都有一个base，就是终止条件
1->2->3->4
// 反转得到p
p
1->2<-3<-4
<-
把p的节点指向head，然后把head释放掉
// 递归，时间空间都是o(n)
public ListNode reverseList(ListNode head) {
if(head==null||head.next==null){
return head;
}
ListNode p=reverseList(head.next);
head.next.next=head;
head.next=null;
return p;
}
// 非递归,时间o(n),空间o(1)
ListNode* reverseList(ListNode* head) {
ListNode *pre=NULL;
ListNode *next=NULL;
if(head==NULL) return NULL;
while(head->next){
next=head->next;
head->next=pre;
pre=head;
head=next;
}
head->next=pre;
return head;
}
3.反转从位置 m 到 n 的链表：递归
// 迭代
// 1->2->3->4->5->6. m=2, n=5
// 1->3->2->4->5->6
// 1->4->3->2->5->6
// 1->5->4->3->2->6
ListNode* reverseBetween(ListNode* head, int m, int n) {
ListNode* dummpy = new ListNode(-1);
dummpy->next = head;
ListNode* pre = dummpy;
for (int i = 0; i < m - 1; i++) {
pre = pre->next;
}
ListNode* cur = pre->next;
for (int i = m; i < n; i++) {
ListNode* next = cur->next;
cur->next = next->next;
next->next = pre->next;
pre->next = next;
}
return dummpy->next;
}
//*************递归************
public ListNode reverseBetween(ListNode head, int m, int n) {
if(m==1){//从第一个位置开始，即返回前n个
return reverseList(head,n);
}
head.next=reverseBetween(head.next,m-1,n-1);
return head;
}
private ListNode successor;
//反转前n个元素
public ListNode reverseList(ListNode head, int n) {
if(n==1){
successor=head.next;//记录后继结点
return head;
}
ListNode p=reverseList(head.next,n-1);
head.next.next=head;
head.next=successor;//将head指向后继，反转整条链表尾null
return p;
}
4.K个一组反转链表：迭代
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
示例：
给你这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5
// *************第一种**********
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode *dummy = new ListNode(-1), *pre = dummy, *cur = pre;
dummy->next = head;
int num = 0;
while (cur = cur->next) ++num;
while (num >= k) {
cur = pre->next;
for (int i = 1; i < k; ++i) {
ListNode *next = cur->next;
cur->next = next->next;
next->next = pre->next;
pre->next = next;
}
pre = cur;
num -= k;
}
return dummy->next;
}
// 翻转一个子链表，并且用head迭代，当head到尾部时，翻转结束
class Solution {
public:
// 翻转一个子链表，并且返回新的头与尾
pair<ListNode*, ListNode*> myReverse(ListNode* head, ListNode* tail) {
ListNode* prev = tail->next;
ListNode* p = head;
while (prev != tail) {
ListNode* nex = p->next;
p->next = prev;
prev = p;
p = nex;
}
return {tail, head};
}
head
// 0->1->2->3->4->5
hair tail
pre
// 找到第一个翻转的tail节点，翻转head，tail节点，得到
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode* hair = new ListNode(0);
hair->next = head;
ListNode* pre = hair;
while (head) {
ListNode* tail = pre;
// 查看剩余部分长度是否大于等于 k，找到头尾链表，然后翻转
for (int i = 0; i < k; ++i) {
tail = tail->next;
if (!tail) {
return hair->next;
}
}
ListNode* nex = tail->next;
// 这里是 C++17 的写法，也可以写成
// pair<ListNode*, ListNode*> result = myReverse(head, tail);
// head = result.first;
// tail = result.second;
tie(head, tail) = myReverse(head, tail);
// 把子链表重新接回原链表
pre->next = head;
tail->next = nex;
pre = tail;
head = tail->next;
}
return hair->next;
}
};
- 两两反转链
// 迭代
ListNode* swapPairs(ListNode* head) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* p = head;
ListNode* pre = dummy;
while (p != NULL && p->next != NULL) {
ListNode* cur = p->next;
ListNode* next = cur->next;
cur->next = p;
pre->next = cur;
pre = p;
p->next = next;
p = next;
}
return dummy->next;
}
// 递归
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode nextHead = swapPairs(head.next.next);
ListNode next = head.next;
next.next = head;
head.next = nextHead;
return next;
}
6.旋转链表
给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]
ListNode* rotateRight(ListNode* head, int k) {
if (head == NULL || k == 0) return head;
ListNode* slow = head;
ListNode* fast = head;
ListNode* p = head;
int size = 1;
while (p->next != NULL) {
p = p->next;
size++;
}
k = k%size;
if (k == 0) return head;
while (k > 0 && fast->next != NULL) {
fast = fast->next;
k--;
}
while (fast->next != NULL) {
fast = fast->next;
slow = slow->next;
}
ListNode* newhead = slow->next;
fast->next = head;
slow->next = NULL;
return newhead;
}
7.分隔链表
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。你应当 保留 两个分区中每个节点的初始相对位置。
输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]
ListNode *partition(ListNode *head, int x) {
ListNode *dummy = new ListNode(-1);
dummy->next = head;
ListNode *pre = dummy, *cur = head;
// 找到值大于x的停止
while (pre->next && pre->next->val < x) pre = pre->next;
cur = pre;
//
while (cur->next) {
if (cur->next->val < x) {
ListNode *tmp = cur->next;
cur->next = tmp->next;
tmp->next = pre->next;
pre->next = tmp;
pre = pre->next;
} else {
cur = cur->next;
}
}
return dummy->next;
}
8.复制带随机指针的链表
时间复杂度：O(n)，其中 n 是链表的长度。我们只需要遍历该链表三次。
空间复杂度：O(1)。注意返回值不计入空间复杂度。
第一种方法：
建立哈希表，然后遍历链表，深复制的同时将复制的旧节点作为key，新节点作为value存进哈希表，
第二次遍历 以原链表的一个节点的随机指针值作为索引，查找对应的新链表的对应节点的随机指针值
第二种方法：将新老链表相互间隔的串为一个链表；然后，处理random指针域；最后，将老新链表拆开，并返回对应的链表头结点。
Node* copyRandomList(Node* head) {
if (head == nullptr) {
return nullptr;
}
// 1、将新老结点串为一个链表
for (Node* node = head; node != nullptr; node = node->next->next) {
Node* nodeNew = new Node(node->val);
nodeNew->next = node->next;
node->next = nodeNew;
}
//2、处理random指针域
for (Node* node = head; node != nullptr; node = node->next->next) {
Node* nodeNew = node->next;
nodeNew->random = (node->random != nullptr) ? node->random->next : nullptr;
}
//3、将老新链表拆开，返回新链表
Node* headNew = head->next;
for (Node* node = head; node != nullptr; node = node->next) {
Node* nodeNew = node->next;
node->next = node->next->next;
nodeNew->next = (nodeNew->next != nullptr) ? nodeNew->next->next : nullptr;
}
return headNew;
}
9.删除链表重复元素
******************第一种，重复一个不留*****************
输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]
ListNode* deleteDuplicates(ListNode* head) {
if (head == NULL) return NULL;
ListNode* pre = new ListNode();
pre->next = head;
ListNode* newhead = pre;
ListNode* cur = head;
while (cur->next!= NULL) {
if(cur->val == cur->next->val) {
while (cur->next != NULL && cur->val == cur->next->val)
cur = cur->next;
if (cur->next == NULL) {
pre->next = NULL;
break;
}
pre->next = cur->next;
cur = cur->next;
} else {
cur = cur->next;
pre = pre->next;
}
}
return newhead->next;
}
********************第二种，重复留一个******************
输入：head = [1,2,3,3,4,4,5]
输出：[1,2,3,4,5]
ListNode* deleteDuplicates(ListNode* head) {
if (head == NULL) return head;
ListNode* pre = new ListNode();
pre->next = head;
ListNode* cur = head;
ListNode* point = pre;
while (cur->next != NULL) {
while (cur->next != NULL && cur->next->val == cur->val) cur = cur->next;
pre->next = cur;
if (cur->next == NULL) {
break;
}
cur = cur->next;
pre = pre->next;
}
return point->next;
}
10.合并k个链表：递归
image.png
# 最简单的方法
ListNode* mergeKLists(vector<ListNode*>& lists) {
if (lists.size()==0) return NULL;
for(int i = 1; i < lists.size(); i++) {
lists[i] = mergeTwoLists(lists[i-1],lists[i]);
}
return lists[lists.size()-1];
}
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (l1 == NULL && l2 == NULL) return NULL;
if (l1 == NULL) return l2;
if (l2 == NULL) return l1;
ListNode* merged;
if (l1->val > l2->val) {
merged = l2;
l2 = l2->next;
merged->next= mergeTwoLists(l1,l2);
} else {
merged = l1;
l1 = l1->next;
merged->next = mergeTwoLists(l1,l2);
}
return merged;
}
# 分治合并，每次把list分成2个
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
return merger(lists, 0, lists.length - 1);
}
private ListNode merger(ListNode[] lists, int l, int r) {
if (l == r) {
return lists[l];
}
if (l > r) {
return null;
}
//右移一位相当于除2
int mid=(l+r)>>1;
return mergeTwoLists(merger(lists,l,mid),merger(lists,mid+1,r));
}
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode pre = new ListNode(0);
ListNode curr = pre;
while (l1 != null || l2 != null) {
if (l1 == null) {
curr.next = l2;
return pre.next;
}
if (l2 == null) {
curr.next = l1;
return pre.next;
}
if (l1.val < l2.val) {
curr.next = l1;
curr = curr.next;
l1 = l1.next;
} else {
curr.next = l2;
curr = curr.next;
l2 = l2.next;
}
}
return pre.next;
}
}
