今天链表面试OJ题目
- 移除链表元素
- 反转链表
- 相交链表
- 链表的中间节点
- 链表中倒数第k个节点
- 合并链表
- 分割链表
- 🙂起始条件 中间节点 结束条件
- 🙂结束条件while易错
- 🙂单独处理头和尾
- 🙂处理链表为NULL的情况
- 🙂释放的先后顺序-----野指针
- 🙂指针的指向问题tail / tail->next
- && || == = (赋值)
- return 返回值的问题
- 🙂往极端情况考虑
1.移除链表元素√
给你一个链表的头节点
head
和一个整数val
,请你删除链表中所有满足Node.val == val
的节点,并返回 新的头节点 。
输入:head = [1,2,6,3,4,5,6], val = 6
输出:[1,2,3,4,5]
【双指针】
struct ListNode* removeElements(struct ListNode* head, int val) { struct ListNode*cur=head; struct ListNode*prve=NULL; while(cur) { if(cur->val == val) { if(prve) { prve->next=prve->next->next; free(cur); cur=prve->next; } else { head=head->next; free(cur); cur=head; } } else { prve=cur; cur=cur->next; } } return head; } cur是指当前节点的指针 prve是指向前一个节点的指针
【三指针不带头节点】
struct ListNode* removeElements(struct ListNode* head, int val) { struct ListNode* cur=head; struct ListNode* tail=NULL; struct ListNode* newhead=NULL; while(cur) { if(cur->val != val) { if(tail) { tail->next=cur;//易错 tail=tail->next; } //处理头 else { newhead=tail=cur;//易错 } cur=cur->next; } else { struct ListNode* tmp=cur->next; free(cur); cur=tmp; } } //处理尾 if(tail) { tail->next=NULL; } return newhead; }
【三指针带头节点】
struct ListNode* removeElements(struct ListNode* head, int val) { struct ListNode* cur=head; struct ListNode* newhead=(struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* tail=newhead; while(cur) { if(cur->val != val) { tail->next=cur; tail=tail->next; cur=cur->next; } else { struct ListNode* tmp=cur->next; free(cur); cur=tmp; } } //处理尾 if(tail) { tail->next=NULL; } struct ListNode*tmp=newhead; newhead=newhead->next; free(tmp); tmp=NULL; return newhead; }
2.反转链表
给你单链表的头节点
head
,请你反转链表,并返回反转后的链表。
输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]
【头插】
struct ListNode* reverseList(struct ListNode* head) { struct ListNode*newhead=NULL; struct ListNode*cur=head; while(cur) { struct ListNode*tmp=cur->next; cur->next=newhead; newhead=cur; cur=tmp; } return newhead; } //可以不用处理头 struct ListNode* reverseList(struct ListNode* head) { struct ListNode*newhead=NULL; struct ListNode*cur=head; while(cur) { struct ListNode*tmp=cur->next; if(newhead == NULL) { newhead = cur; newhead->next = NULL;//易错 } else { cur->next=newhead; newhead=cur; } cur=tmp; } return newhead; }
【三指针】
struct ListNode* reverseList(struct ListNode* head) { if(head == NULL) { return NULL; } struct ListNode*n1=NULL; struct ListNode*n2=head; struct ListNode*n3=head->next; while(n2)//易错 { n2->next=n1; n1=n2; n2=n3; if(n3) n3=n3->next; } return n1;//易错 }
3.相交链表
给你两个单链表的头节点
headA
和headB
,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回null
。图示两个链表在节点
c1
开始相交:题目数据 保证 整个链式结构中不存在环。
注意,函数返回结果后,链表必须 保持其原始结构 。
输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出:Intersected at '8'
解释:相交节点的值为 8 (注意,如果两个链表相交则不能为 0)。
从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,6,1,8,4,5]。
在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。
— 请注意相交节点的值不为 1,因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说,它们在内存中指向两个不同的位置,而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点,B 中第四个节点) 在内存中指向相同的位置。
【双指针】
- 题目中有明确的说明两个链表都不为NULL
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { int A=1; int B=1; struct ListNode *curA=headA; struct ListNode *curB=headB; int N=0; while(curA->next) { A++; curA=curA->next; } while(curB->next) { B++; curB=curB->next; } if(curA != curB) { return NULL; } else { N=abs(A-B); if(A>B) { while(N--) { headA=headA->next; } while(headA != headB) { headA=headA->next; headB=headB->next; } return headA; } else { while(N--) { headB=headB->next; } while(headA != headB) { headA=headA->next; headB=headB->next; } return headA; } } }
【简化】
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { int A=1; int B=1; struct ListNode *curA=headA; struct ListNode *curB=headB; int N=0; while(curA->next) { A++; curA=curA->next; } while(curB->next) { B++; curB=curB->next; } if(curA != curB) { return NULL; } else { N=abs(A-B); //简写------假设法 struct ListNode *longlist=headA; struct ListNode *shortlist=headB; if(B>A) { longlist=headB; shortlist=headA; } // while(N--) { longlist=longlist->next; } while(longlist != shortlist) { longlist=longlist->next; shortlist=shortlist->next; } return longlist; } }
4.链表的中间节点
给你单链表的头结点
head
,请你找出并返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点。
输入:head = [1,2,3,4,5]
输出:[3,4,5]
解释:链表只有一个中间结点,值为 3 。
【快慢双指针】
- 保持相对速度
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* middleNode(struct ListNode* head) { struct ListNode*faster=head; struct ListNode*slow=head; while(faster && faster->next)//条件没想到 { faster=faster->next->next; slow=slow->next; } return slow; }
5.链表中倒数第k个节点
输入一个链表,输出该链表中倒数第k个结点
示例1:输入:1,{1,2,3,4,5}
返回值:{5}
示例2:输入:6,{1,2,3,4,5}
返回值:{}
【快慢指针】
- 保持相对距离
-----------【k步】
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { struct ListNode*faster=pListHead; struct ListNode*slow=pListHead; while(k--)//走k { if(faster == NULL) { return NULL; } faster=faster->next; } while(faster) { faster=faster->next; slow=slow->next; } return slow; }
----------------【k-1步】
/** * struct ListNode { * int val; * struct ListNode *next; * }; */ /** * * @param pListHead ListNode类 * @param k int整型 * @return ListNode类 */ struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { struct ListNode*faster=pListHead; struct ListNode*slow=pListHead; while(--k)//走k-1 { if(faster == NULL) { return NULL; } faster=faster->next; } //当循环结束的时候faster为NULL if(faster == NULL)//判断一下即可乖乖 return NULL; while(faster->next) { faster=faster->next; slow=slow->next; } return slow; }
6.合并链表√
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4
【三指针带头】
- 取小尾插
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { struct ListNode*cur1=list1; struct ListNode*cur2=list2; struct ListNode*newhead=NULL; struct ListNode*tail=NULL; if(list1 == NULL) return list2; if(list2 == NULL) return list1; while(cur1 && cur2) { if(cur1->val <= cur2->val) { if(newhead == NULL) { newhead=tail=cur1;//易错 } else { tail->next=cur1;//已经放进去//易错 tail=tail->next;//tail是尾节点,可以往后移动了 } cur1=cur1->next; } else { if(newhead == NULL) { newhead=tail=cur2; } else { tail->next=cur2;//已经放进去 tail=tail->next;//tail是尾节点,可以往后移动了 } cur2=cur2->next; } } if(cur1 == NULL) { tail->next=cur2; } else { tail->next=cur1;//已经不用在往后走了 } return newhead; }
7.分割链表√
现有一链表的头指针 ListNode* pHead,给一定值x,编写一段代码将所有小于x的结点排在其余结点之前,且不能改变原来的数据顺序,返回重新排列后的链表的头指针。
【三指针带头】
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} };*/ //用不带头节点来写,两个链表都可能为NULL,都要判断非常麻烦 //所以我们用带头节点来写 class Partition { public: ListNode* partition(ListNode* pHead, int x) { ListNode* list1=(ListNode*)malloc(sizeof(ListNode)); ListNode* list2=(ListNode*)malloc(sizeof(ListNode)); ListNode* tail1=list1; ListNode* tail2=list2; ListNode* cur=pHead; while(cur) { if(cur->val < x) { tail1->next=cur; tail1=tail1->next; } else//cur->val >= x { tail2->next=cur; tail2=tail2->next; } cur=cur->next; } //尾巴处理 tail1->next=list2->next; tail2->next=NULL;//易错 return list1->next; } };
❓我们√三道题都有异曲同工之妙。
代码---------→【唐棣棣 (TSQXG) - Gitee.com】
联系---------→【邮箱:2784139418@qq.com】