LeetCode链表解题模板

时间:2024-08-30 15:34:50

一、通用方法以及题目分类

0、遍历链表

方法代码如下,head可以为空:

ListNode* p = head;
while(p!=NULL)
p = p->next;

可以在这个代码上进行修改,比如要计算链表的长度:

ListNode* p = head;
int num = ;
while(p!=NULL){
num++;
p = p->next;
}

如果要找到最后的节点,可以更改while循环中的条件,只不过需要加上head为NULL时的判断

if(!head) return head;
ListNode* p = head;
while(p->next!=NULL){
p = p->next;
}

还可以使用两个指针,一个用来遍历,一个用来记录前一个

ListNode* p_before = NULL;
ListNode* p = head;
while(p!=NULL){
p_before = p;
p = p->next;
}

1、在head之前加上一个节点来简化计算

头结点的操作不同于中间节点,所以需要额外判断。穿插在很多题目中。

LeetCode 203 删除节点中的元素:https://leetcode.com/problems/remove-linked-list-elements/description/

2、两链表合并操作

l1代表链表1的头,l2代表链表2的头,通过以下方式来遍历链表(或是将while循环中的&&改成||)

while循环中如果是&&,则退出循环需要处理一个为空、一个还有的情况。如果while循环中为||,则在while循环体中需要判断其中一个为空的情况

还可以联合前一种方式,在head之前加上一个节点来简化计算

while(l1!=NULL && l2!=NULL){
if(l1 != NULL){
//operator on l1
l1 = l1->next;
}
if(l2 != NULL){
//operator on l2
l2 = l2->next;
}
}
//operator on the remain

比如LeetCode2的两链表数相加的题:

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* result = new ListNode();
ListNode* current = result;
int add = ;
while(l1!=NULL || l2!=NULL || add!=){
int num1 = ;
int num2 = ;
if(l1 != NULL){
num1 = l1->val;
l1 = l1->next;
}
if(l2 != NULL){
num2 = l2->val;
l2 = l2->next;
}
ListNode* t = new ListNode((num1+num2+add)%);
add = (num1+num2+add)>=?:;
current->next = t;
current = t;
}
return result->next;
}

LeetCode2 两数相加:https://leetcode.com/problems/add-two-numbers/description/

LeetCode21 合并两链表:https://leetcode.com/problems/merge-two-sorted-lists/description/

LeetCode86 划分链表:https://leetcode.com/problems/partition-list/description/

LeetCode328 奇偶链表:https://leetcode.com/problems/odd-even-linked-list/description/

3、前后指针

l1在前,l2在后,让l2先走n步,当退出第二个循环时,l2位空,l1为倒数第n个节点。可以判断链表是否有环,确定环出现的位置等

ListNode* l1 = head;
ListNode* l2 = head;
while(n-->){
l2 = l2->next;
}
while(l2 !=NULL){
l1 = l1->next;
l2 = l2->next;
}

利用快慢指针可以找到链表的中间节点,l1每次向前走一格,l2每次向前走两个。

当l1、l2都从head开始时,while循环退出时,如果是链表节点数是奇数,则l1指向正中间,如果是偶数,则l1指向位置为中间后一个,例:如果有4个,则l1指向第3个

ListNode* l1 = head;
ListNode* l2 = head;
while (l2 != NULL && l2->next!= NULL) {
l1 = l1->next;
l2 = l2->next->next;
}

当l1从head,l2从head->next开始,while循环退出时,如果是链表节点数是奇数,则l1指向正中间,如果是偶数,则l1指向位置为正中间,例:如果有4个,则l1指向第2个

ListNode* l1 = head;
ListNode* l2 = head->next;
while (l2 != NULL && l2->next!= NULL) {
  l1 = l1->next;
  l2 = l2->next->next;
}

LeetCode19 移除倒数第n个数:https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/

LeetCode109 将链表转化为二叉树:https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/description/

LeetCode141 判断链表是否有环:https://leetcode.com/problems/linked-list-cycle/description/

LeetCode142 找出链表有环的位置:https://leetcode.com/problems/linked-list-cycle-ii/description/

LeetCode160 找出两链表的交叉点:https://leetcode.com/problems/intersection-of-two-linked-lists/description/

287. Find the Duplicate Number https://leetcode.com/problems/find-the-duplicate-number/description/

数组的快慢指针

class Solution {
public:
int findDuplicate(vector<int>& nums) {
if(nums.size()<) return -;
int pos1 = nums[];
int pos2 = nums[pos1];
while(pos1!=pos2){
pos1 = nums[pos1];
pos2 = nums[nums[pos2]];
}
pos1 = ;
while(pos1!=pos2){
pos1 = nums[pos1];
pos2 = nums[pos2];
}
return pos1;
}
};

1、数组也会形成环,同160的思路

4、利用前后指针处理链表内部数据,综合前几种处理方式

同样是l1和l2指针,一个在前一个在后,只是通过这样遍历一遍需要对链表中的数据进行修改。

思考方式:

1、假设进行中间某一点,看需要保存那些位置的值,即考虑n到n+1的情况

2、查看边界条件,开始位置的边界,结束位置的边界

反转链表的操作如下,注意将l1初始化为NULL,这样在反转之后可以让尾部节点为空

ListNode* reverse(ListNode* head){
  if(head == NULL || head->next == NULL) return head;
  ListNode* l1 = NULL;
  ListNode* l2 = head;
  while(l2){
    ListNode* t = l2->next;
    l2->next = l1;
    l1 = l2;
    l2 = t;
  }
  return l1;
}

LeetCode24 反转链表中的元素:https://leetcode.com/problems/swap-nodes-in-pairs/description/

LeetCode61 旋转链表:https://leetcode.com/problems/rotate-list/description/

LeetCode83 https://leetcode.com/problems/remove-duplicates-from-sorted-list/description/

LeetCode82 https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/description/

LeetCode206 颠倒链表:https://leetcode.com/problems/reverse-linked-list/description/

1、取中间某一个位置,如果需要颠倒链表,需要保存两个值,一个是前面的指针,一个是当前指针,让当前指针的next指向前一个指针,然后两个指针整体向后移动一位,此时由于当前的next被修改了,所以next的位置需要提前被保存起来

2、考虑边界值,开始时前一个指针需要被设置为NULL,结束时,当前指针为NULL,前一个指针指向最后一个元素。

LeetCode143 重新整理链表 https://leetcode.com/problems/reorder-list/description/

是以上几种题型的综合,既有快慢指针,又有反转链表,还有合并链表

LeetCode234 回文链表 https://leetcode.com/problems/palindrome-linked-list/description/

LeetCode445 反向相加两数 https://leetcode.com/problems/add-two-numbers-ii/description/

5、链表排序

LeetCode 147 链表的插入排序:https://leetcode.com/problems/insertion-sort-list/description/

LeetCode 148 链表的归并排序:https://leetcode.com/problems/sort-list/description/

6、其他

LeetCode 237 删除节点:https://leetcode.com/problems/delete-node-in-a-linked-list/description/

LeetCode 430 铺展多级链表:https://leetcode.com/problems/flatten-a-multilevel-doubly-linked-list/description/

二、答案以及边界情况

LeetCode2:

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* result = new ListNode();
ListNode* current = result;
int add = ;
while(l1!=NULL || l2!=NULL || add!=){
int num1 = ;
int num2 = ;
if(l1 != NULL){
num1 = l1->val;
l1 = l1->next;
}
if(l2 != NULL){
num2 = l2->val;
l2 = l2->next;
}
ListNode* t = new ListNode((num1+num2+add)%);
add = (num1+num2+add)>=?:;
current->next = t;
current = t;
}
return result->next;
}

LeetCode2

1、while循环中未加入add

2、add的再次计算以及新建ListNode的取值

3、加入头结点来简化不断增加链表的操作,不加时则需要额外判断第一个节点加入的情况

LeetCode19:

1、当链表长度为n时会出现删除头节点的情况,加上一个头节点可以简化这种操作

LeetCode21:

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode l();
ListNode* current = &l;
while(l1!=NULL&&l2!=NULL){
if(l1->val < l2->val){
current->next = l1;
l1 = l1->next;
}else{
current->next = l2;
l2 = l2->next;
}
current = current->next;
}
if(l1 == NULL)
current->next = l2;
if(l2 == NULL)
current->next = l1;
return l.next;
}

LeetCode21

1、while循环中入股哦是&&,则退出循环需要处理一个为空、一个还有的情况。如果while循环中为||,则在while循环体中需要判断其中一个为空的情况

LeetCode24:

ListNode* swapPairs(ListNode* head) {
if(head == NULL) return head;
ListNode l1();
l1.next = head;
ListNode* before = &l1;
ListNode* t1 = head;
ListNode* t2 = head->next;
while(t1!=NULL && t2!=NULL){
t1->next = t2->next;
t2->next = t1;
before->next = t2;
t1 = t1->next;
if(t1!=NULL) t2 = t1->next;
before = before->next->next;
}
return l1.next;
}

LeetCode24

1、明白反转链表需要哪几个节点的值再思考

2、这里需要保存before,但是出现了头节点可能为空的情况

LeetCode61:旋转链表

总体思路还是前后指针,但k可能大于链表长度,所以前指针先走的步数不确定

解法一:前进k步,如果到达链表末尾时还未走k步,则说明k大于链表长度。需要重新从头走k%lenth步。然后前后指针同时向后走,到达末尾后反转。

ListNode* rotateRight(ListNode* head, int k) {
if(head == NULL || k == ) return head;
int temp = k;
ListNode t();
t.next = head;
ListNode* p1 = head;
ListNode* before1 = &t;
int num = ;
while(p1!=NULL && k-->){
num++;
before1 = before1->next;
p1 = p1->next;
}
if(p1 == NULL){
k = temp%num;
if(temp%num == ) return head;
p1 = head;
before1 = &t;
while(k-->){
before1 = before1->next;
p1 = p1->next;
}
} ListNode* p2 = head;
ListNode* before2 = &t;
while(p1!=NULL){
p1 = p1->next;
p2 = p2->next;
before1 = before1->next;
before2 = before2->next;
}
before2->next = NULL;
before1->next = head;
return p2;
}

LeetCode61

1、如果k==0,也就是最后一步的链表断裂和重新连接的步骤的位置都是同一个,则会形成环,这里需要特别注意(head是绝对位置,before1和before2都是相对位置,当出现这类型赋值时一定要考虑边界条件

2、head == NULL时,num为0,在除的时候num不能为0,所以开头需要除去head==NULL的情况

3、在判断k==0时候要注意位置,在对k取余数的时候也会出现余数为0的情况,所以也需要额外的判断k==0

4、k在循环的时候是不断递减的,需要先保存以下k的值。

解法二:将链表变成循环链表。相比上一个方法,边界条件少了很多,代码也不容易写错,更加简洁

    ListNode* rotateRight(ListNode* head, int k) {
if(!head) return head;
ListNode* p = head;
int length = ;
while(p->next!=NULL){
p = p->next;
length++;
}
p->next = head;
for(size_t i = ;i<length-k%length;i++){
p = p->next;
}
ListNode* result = p->next;
p->next = NULL;
return result;
}

LeetCode61

1、注意第一次while循环中的条件

2、求出链表长度之后,开始遍历的位置是尾部,以及遍历的长度是length-k。这点需要明确。

LeetCode82:消除重复元素2

ListNode* deleteDuplicates(ListNode* head) {
ListNode* p = head;
ListNode t();
t.next = head;
ListNode* before = &t;
while(p!=NULL){
int num = p->val;
p = p->next;
bool change = false;
while(p!=NULL && p->val == num){
change = true;
p = p->next;
}
if(change){
before->next = p;
}else{
before = before->next;
}
}
return t.next;
}

LeetCode82

LeetCode82:消除重复元素

ListNode* deleteDuplicates(ListNode* head) {
ListNode* p = head;
ListNode t();
t.next = head;
while(p!=NULL){
int num = p->val;
ListNode* c = p;
p = p->next;
while(p!=NULL && p->val == num){
p = p->next;
}
c->next = p;
c = c->next;
}
return t.next;
}

LeetCode83

LeetCode86:分割链表

ListNode* partition(ListNode* head, int x) {
ListNode t1();
ListNode t2();
ListNode* less = &t1;
ListNode* bigger = &t2;
ListNode* current = head;
while(current!=NULL){
if(current->val < x){
less->next = current;
less = less->next;
}else{
bigger->next = current;
bigger = bigger->next;
}
current = current->next;
}
bigger->next = NULL;
less->next = t2.next;
return t1.next;
}

leetCode86

1、注意退出while循环后将两个分别的链表拼起来的时候,大于val的链表尾部要设为空。

LeetCode206:颠倒链表

ListNode* reverseList(ListNode* head) {
ListNode* before = NULL;
while(head){
ListNode* t = head->next;
head->next = before;
before = head;
head = t;
}
return before;
}

LeetCode206

LeetCode206:颠倒链表2

ListNode t();
t.next = head;
ListNode* before_m;
ListNode* _m;
ListNode* _n;
ListNode* later_n;
ListNode* current = head;
ListNode* before = &t;
int num = ;
while(current){
num++;
if(num<m){
before = current;
current = current->next;
}else if(num == m){
before_m = before;
_m = current;
ListNode* t = current->next;
current->next = NULL;
before = current;
current = t;
}else if(num <= n){
ListNode* t = current->next;
current->next = before;
before = current;
current = t;
}else{
break;
}
}
_n = before;
later_n = current; before_m->next = _n;
_m->next = later_n;
return t.next;

LeetCode92

完成整个大的目标需要两个条件

1、翻转m到n的链表

2、将before_m的next指向n,m的next指向later_n

然后遍历,在遍历过程中对几个过程进行处理,小于m时,等于m时,大于m小于等于n时

LeetCode109:将链表转化为二叉树

TreeNode* sortedListToBST(ListNode* head) {
if(head == NULL) return NULL;
if(head->next == NULL){
TreeNode* result = new TreeNode(head->val);
return result;
}
ListNode* before_l1 = NULL;
ListNode* l1 = head;
ListNode* l2 = head->next;
while(l2!=NULL && l2->next!=NULL){
before_l1 = l1;
l1 = l1->next;
l2 = l2->next->next;
}
TreeNode* node = new TreeNode(l1->val);
if(before_l1 == NULL){
node->left = sortedListToBST(NULL);
}else{
before_l1->next = NULL;
node->left = sortedListToBST(head);
}
node->right = sortedListToBST(l1->next);
return node;
}

LeetCode109

1、需要注意的是在将链表断成3个部分的时候前一部分有额外情况,那就是链表只有两个节点的时候,l1指向第一个节点,前一部分应该为NULL

LeetCode138:复制随机链表的指针

RandomListNode* copyRandomList(RandomListNode *head, map<int, RandomListNode*>& m) {
if (head == NULL) return NULL;
if (m.find(head->label) == m.end()) {
RandomListNode* t = new RandomListNode(head->label);
m.insert(pair<int, RandomListNode*>(head->label, t));
t->next = copyRandomList(head->next, m);
t->random = copyRandomList(head->random, m);
return t;
}
else {
return (*m.find(head->label)).second;
}
}
RandomListNode *copyRandomList(RandomListNode *head) {
if (head == NULL) return NULL;
map<int,RandomListNode*> m;
return copyRandomList(head,m);
}

LeetCode138

LeetCode141 判断链表是否有环:

bool hasCycle(ListNode *head) {
if(head == NULL) return false;
ListNode t();
t.next = head;
ListNode* l1 = &t;
ListNode* l2 = &t;
while(l2!=NULL && l2->next!=NULL){
l1 = l1->next;
l2 = l2->next->next;
if(l1 == l2) return true;
}
return false;
}

leetCode141

1、判断l1等于l2的位置不能写错

LeetCode142 找出链表有环的位置

ListNode *detectCycle(ListNode *head) {
if(!head) return NULL;
ListNode t();
t.next = head;
ListNode* l1 = head;
ListNode* l2 = head;
while(l2!=NULL && l2->next!=NULL){
l1 = l1->next;
l2 = l2->next->next;
if(l1 == l2) break;
}
if(l2 == NULL || l2->next == NULL) return NULL;
ListNode* l3 = head;
while(l1 != l3){
l1 = l1->next;
l3 = l3->next;
}
return l1;
}

LeetCode142

1、本题链表可能没有环

LeetCode143 重新整理链表

void reorderList(ListNode* head) {
if(head == NULL || head->next == NULL) return ;
ListNode* l1 = head;
ListNode* l2 = head->next;
while(l2 != NULL && l2->next!=NULL){
l1 = l1->next;
l2 = l2->next->next;
}
ListNode* head2 = l1->next;
l1->next = NULL;
l1 = NULL;
while(head2 != NULL){
ListNode* t = head2->next;
head2->next = l1;
l1 = head2;
head2 = t;
}
//l1是反向链表的头
ListNode t();
ListNode* result = &t;
while(l1 != NULL || head!=NULL){
if(head!=NULL){
result->next = head;
head = head->next;
result = result->next;
}
if(l1 != NULL){
result->next = l1;
l1 = l1->next;
result = result->next;
}
}
head = t.next;
return ;
}

LeetCode 143

LeetCode 147 链表的插入排序

ListNode* insertionSortList(ListNode* head) {
ListNode t(INT_MIN);
t.next = NULL;
ListNode* l1 = head;
while (l1 != NULL) {
//删除l1节点
ListNode* next = l1->next;
//从头寻找插入点
ListNode* before_current = &t;
ListNode* current = t.next;
while (current != NULL && current->val<l1->val) {
before_current = before_current->next;
current = current->next;
}
l1->next = current;
before_current->next = l1; l1 = next;
}
return t.next;
}

LeetCode 147

LeetCode 148 链表的归并排序

ListNode* merge(ListNode* l1, ListNode* l2) {
ListNode temp(-);
ListNode* result = &temp;
while (l1 != NULL && l2 != NULL) {
if (l1->val > l2->val) {
result->next = l2;
l2 = l2->next;
}else {
result->next = l1;
l1 = l1->next;
}
result = result->next;
}
if (l1 == NULL)
result->next = l2;
else
result->next = l1;
return temp.next;
}
ListNode* sortList(ListNode* head) {
if (head == NULL || head->next == NULL) return head;
ListNode* l1 = head;
ListNode* l2 = head->next;
while (l2 != NULL && l2->next!= NULL) {
l1 = l1->next;
l2 = l2->next->next;
}
//l1是中间节点
l2 = l1->next;
l1->next = NULL; return merge(sortList(head), sortList(l2));
}

LeetCode 148

LeetCode160 找出两链表的交叉点

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int lengthA = ;
ListNode* l = headA;
while(l!=NULL){
lengthA++;
l = l->next;
}
int lengthB = ;
l = headB;
while(l!=NULL){
lengthB++;
l = l->next;
}
ListNode* l1 = headA;
ListNode* l2 = headB;
if(lengthA<lengthB){
int t = lengthB-lengthA;
for(size_t i =;i<t;i++)
l2 = l2->next;
}else{
int t = lengthA-lengthB;
for(size_t i =;i<t;i++)
l1 = l1->next;
}
while(l1 != l2){
l1 = l1->next;
l2 = l2->next;
}
return l1;
}

LeetCode 160

LeetCode 203 删除节点中的元素

ListNode* removeElements(ListNode* head, int val) {
if (head == NULL ) return NULL;
ListNode* l = head;
ListNode t(-);
t.next = head;
ListNode* l_before = &t;
while (l) {
if (l->val == val)
l_before->next = l->next;
else
l_before = l;
l = l->next;
}
return t.next;
}

LeetCode203

LeetCode234 回文链表

bool isPalindrome(ListNode* head) {
if(head == NULL || head->next == NULL) return true;
ListNode* l1 = head;
ListNode* l2 = head->next;
while(l2!=NULL && l2->next!=NULL){
l1 = l1->next;
l2 = l2->next->next;
}
l2 = l1->next;
l1->next = NULL;
l1 = NULL;
while(l2 != NULL){
ListNode* t = l2->next;
l2->next = l1;
l1 = l2;
l2 = t;
}
//l1是后一部分的头
while(l1!=NULL && head!=NULL){
if(l1->val != head->val) return false;
l1 = l1->next;
head = head->next;
}
return true;
}

LeetCode 234

1、注意就情况的区分

LeetCode 237 删除节点

void deleteNode(ListNode* node) {
if (!node || !node->next)
return;
node->val = node->next->val;
node->next = node->next->next;
}

LeetCode237

LeetCode328 奇偶链表

ListNode* oddEvenList(ListNode* head) {
if(head == NULL || head->next == NULL) return head;
ListNode* head1 = head,*current1 = head;
ListNode* head2 = head->next,*current2 = head->next;
ListNode* current = head->next->next;
while(current != NULL){
current1->next = current;
current1 = current1->next;
current = current->next;
if(current != NULL){
current2->next = current;
current2 = current2->next;
current = current->next;
}
}
current1->next = head2;
current2->next = NULL;
return head1;
}

LeetCode 328

LeetCode445 反向相加两数

ListNode* reverse(ListNode* head){
if(head == NULL || head->next == NULL) return head;
ListNode* l1 = NULL;
ListNode* l2 = head;
while(l2){
ListNode* t = l2->next;
l2->next = l1;
l1 = l2;
l2 = t;
}
return l1;
}
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* new1 = reverse(l1);
ListNode* new2 = reverse(l2);
//加两个链表,前面有一个题和这里一模一样
int add = ;
ListNode* current1 = new1;
ListNode* current2 = new2;
ListNode result();
ListNode* current = &result;
while(current1 || current2 || add==){
int num1 = ;
int num2 = ;
if(current1){
num1 = current1->val;
current1 = current1->next;
}
if(current2) {
num2 = current2->val;
current2 = current2->next;
}
current->next = new ListNode((num1+num2+add)%);
add = (num1+num2+add)/;
current = current->next;
} return reverse(result.next);
}

LeetCode 445

LeetCode 430 铺展多级链表

Node* flatten(Node* head) {
if(head == NULL || (head->child == NULL && head->next == NULL)) return head;
if(head->child == NULL ) {
head->next = flatten(head->next);
head->next->prev = head;
return head;
}else if(head->next == NULL){
head->next = flatten(head->child);
head->next->prev = head;
head->child = NULL;
return head;
}else{
Node* n = flatten(head->next);
Node* c = flatten(head->child);
head->next = c;
c->prev = head;
Node* t = head;
while(c->next!=NULL){
c = c->next;
}
c->next = n;
n->prev = c;
head->child = NULL;
return head;
}
}

LeetCode 430

这题和链表相关不大,会递归或是迭代的写法都可以。

三、复习题目

61

109

141

143

147

148

287