链表常见题目总结
发布时间：2020-12-15 07:59:39 所属栏目：Java 来源：网络整理
导读：1.从尾到头打印链表 题目描述： 输入一个链表，返回一个反序的链表。 实现代码： class Solution { public : ???? vector int printListFromTailToHead ( ListNode * head ) { ???????? stack int nodes ; ???????? vector int result ; ???????? ListNode *
1.从尾到头打印链表题目描述： 输入一个链表，返回一个反序的链表。 实现代码：
class Solution {
public:
????vector<int> printListFromTailToHead(ListNode* head) {
????????stack<int> nodes;
????????vector<int> result;
????????ListNode* node = head;
????????while(node != NULL){
????????????nodes.push(node->val);
????????????node = node->next;
????????}
????????
????????while(!nodes.empty()){
????????????result.push_back(nodes.top());
????????????nodes.pop();
????????}
????????return result;
????}
};
2.链表中倒数第k个节点
题目描述：
输入一个链表，输出该链表中倒数第k个结点。
实现代码：
class Solution {
public:
????ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
????????if(pListHead == NULL || k == 0){
????????????return NULL;
????????}
????????ListNode *pAhead = pListHead;
????????ListNode *pBehind = pListHead;
????????for(unsigned int i = 0; i < k - 1; i++){
????????????if(pAhead->next != NULL){
????????????????pAhead = pAhead->next;
????????????}
????????????else{
????????????????return NULL;
????????????}
????????}
????????while(pAhead->next != NULL){
????????????pAhead = pAhead->next;
????????????pBehind = pBehind->next;
????????}
????????return pBehind;
????}
};
3.反转链表
题目描述：
输入一个链表，反转链表后，输出链表的所有元素。
实现代码：
class Solution {
public:
????ListNode* ReverseList(ListNode* pHead) {
????????ListNode* pReversedHead = NULL;
????????ListNode* pNode = pHead;
????????ListNode* pPrev = NULL;
????????while(pNode != NULL){
????????????ListNode* pNext = pNode->next;
????????????if(pNext == NULL){
????????????????pReversedHead = pNode;
????????????}
????????????pNode->next = pPrev;
????????????pPrev = pNode;
????????????pNode = pNext;
????????}
????????return pReversedHead;
????}
};
4.合并两个排序链表
题目描述：
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
实现代码：
class Solution {
public:
????ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
????{
????????//判断指针是否为空
????????if(pHead1 == NULL){
????????????return pHead2;
????????}
????????else if(pHead2 == NULL){
????????????return pHead1;
????????}
????????ListNode* pMergedHead = NULL;
????????if(pHead1->val < pHead2->val){
????????????pMergedHead = pHead1;
?????????? ????pMergedHead->next = Merge(pHead1->next, pHead2);
????????}
????????else{
????????????pMergedHead = pHead2;
?????????? ????pMergedHead->next = Merge(pHead1, pHead2->next);
????????}
????????return pMergedHead;
????}
};
5.复杂链表的复制
题目描述：
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
实现代码：
class Solution {
public:
????
????//第一步，复制复杂指针的label和next
????void CloneNodes(RandomListNode* pHead){
????????RandomListNode* pNode = pHead;
????????while(pNode != NULL){
????????????RandomListNode* pCloned = new RandomListNode(0);
????????????pCloned->label = pNode->label;
????????????pCloned->next = pNode->next;
????????????pCloned->random = NULL;
????????????
????????????pNode->next = pCloned;
????????????pNode = pCloned->next;
????????}
????}
????
????//第二步，处理复杂指针的random
????void ConnectSiblingNodes(RandomListNode* pHead){
????????RandomListNode* pNode = pHead;
????????while(pNode != NULL){
????????????RandomListNode* pCloned = pNode->next;
????????????if(pNode->random != NULL){
????????????????pCloned->random = pNode->random->next;
????????????}
????????????pNode = pCloned->next;
????????}
????}
????
????//第三步，拆分复杂指针
????RandomListNode* ReconnectNodes(RandomListNode* pHead){
????????RandomListNode* pNode = pHead;
????????RandomListNode* pClonedHead = NULL;
????????RandomListNode* pClonedNode = NULL;
????????
????????if(pNode != NULL){
????????????pClonedHead = pClonedNode = pNode->next;
????????????pNode->next = pClonedNode->next;
????????????pNode = pNode->next;
????????}
????????
????????while(pNode != NULL){
????????????pClonedNode->next = pNode->next;
????????????pClonedNode = pClonedNode->next;
????????????pNode->next = pClonedNode->next;
????????????pNode = pNode->next;
????????}
????????return pClonedHead;
????}
????
????RandomListNode* Clone(RandomListNode* pHead)
????{
????????CloneNodes(pHead);
????????ConnectSiblingNodes(pHead);
????????return ReconnectNodes(pHead);
????}
};
6.两个链表的第一个公共节点
问题描述：
输入两个链表，找出它们的第一个公共结点。
实现代码：
class Solution {
public:
????ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
????????// 如果有一个链表为空，则返回结果为空
????????if(pHead1 == NULL || pHead2 == NULL){
????????????return NULL;
????????}
????????// 获得两个链表的长度
????????unsigned int len1 = GetListLength(pHead1);
????????unsigned int len2 = GetListLength(pHead2);
????????// 默认 pHead1 长， pHead2短，如果不是，再更改
????????ListNode* pHeadLong = pHead1;
????????ListNode* pHeadShort = pHead2;
????????int LengthDif = len1 - len2;
????????// 如果 pHead1 比 pHead2 小
????????if(len1 < len2){
????????????ListNode* pHeadLong = pHead2;
????????????ListNode* pHeadShort = pHead1;
????????????int LengthDif = len2 - len1;
????????}
????????// 将长链表的前面部分去掉，使两个链表等长
????????for(int i = 0; i < LengthDif; i++){
????????????pHeadLong = pHeadLong->next;
????????}
????????
????????while(pHeadLong != NULL && pHeadShort != NULL && pHeadLong != pHeadShort){
????????????pHeadLong = pHeadLong->next;
????????????pHeadShort = pHeadShort->next;
????????}
????????return pHeadLong;
????}
private:
????// 获得链表长度
????unsigned int GetListLength(ListNode* pHead){
????????if(pHead == NULL){
????????????return 0;
????????}
????????unsigned int length = 1;
????????while(pHead->next != NULL){
????????????pHead = pHead->next;
????????????length++;
????????}
????????return length;
????}
};
7.链表中环的入口节点
题目描述：
一个链表中包含环，请找出该链表的环的入口结点。
实现代码：
class Solution {
public:
????ListNode* EntryNodeOfLoop(ListNode* pHead)
????{
????????if(pHead == NULL){
????????????return NULL;
????????}
????????ListNode* meetingnode = MeetingNode(pHead);
????????if(meetingnode == NULL){
????????????return NULL;
????????}
????????// 回环链表结点个数
????????int nodesloop = 1;
????????// 找到环中结点个数
????????ListNode* pNode1 = meetingnode;
????????while(pNode1->next != meetingnode){
????????????pNode1 = pNode1->next;
????????????nodesloop++;
????????}
????????pNode1 = pHead;
????????// 第一个指针向前移动nodesloop步
????????for(int i = 0; i < nodesloop; i++){
????????????pNode1 = pNode1->next;
????????}
????????// 两个指针同时移动，找到环入口
????????ListNode* pNode2 = pHead;
????????while(pNode1 != pNode2){
????????????pNode1 = pNode1->next;
????????????pNode2 = pNode2->next;
????????}
????????return pNode1;
????}
private:
????// 使用快慢指针，找到任意的一个环中结点
????ListNode* MeetingNode(ListNode* pHead){
????????ListNode* pSlow = pHead->next;
????????if(pSlow == NULL){
????????????return NULL;
????????}
????????ListNode* pFast = pSlow->next;
????????while(pFast != NULL && pSlow != NULL){
????????????if(pFast == pSlow){
????????????????return pFast;
????????????}
????????????pSlow = pSlow->next;
????????????pFast = pFast->next;
????????????if(pFast != NULL){
????????????????pFast = pFast->next;
????????????}
????????}
????????return NULL;
????}
};
8.删除链表中重复节点
题目描述：
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5。
实现代码：
class Solution {
public:
????ListNode* deleteDuplication(ListNode* pHead)
????{
????????if(pHead == NULL){
????????????return NULL;
????????}
????????// 指向当前结点前最晚访问过的不重复结点
????????ListNode* pPre = NULL;
????????// 指向当前处理的结点
????????ListNode* pCur = pHead;
????????// 指向当前结点后面的结点
????????ListNode* pNext = NULL;
????????
????????while(pCur != NULL){
????????????// 如果当前结点与下一个结点相同
????????????if(pCur->next != NULL && pCur->val == pCur->next->val){
????????????????pNext = pCur->next;
????????????????// 找到不重复的最后一个结点位置
????????????????while(pNext->next != NULL && pNext->next->val == pCur->val){
????????????????????pNext = pNext->next;
????????????????}
????????????????// 如果pCur指向链表中第一个元素，pCur -> ... -> pNext ->...
????????????????// 要删除pCur到pNext,将指向链表第一个元素的指针pHead指向pNext->next。
????????????????if(pCur == pHead){
????????????????????pHead = pNext->next;
????????????????}
????????????????// 如果pCur不指向链表中第一个元素，pPre -> pCur ->...->pNext ->...
????????????????// 要删除pCur到pNext，即pPre->next = pNext->next
????????????????else{
????????????????????pPre->next = pNext->next;
????????????????}
????????????????// 向前移动
????????????????pCur = pNext->next;
????????????}
????????????// 如果当前结点与下一个结点不相同
????????????else{
????????????????pPre = pCur;
????????????????pCur = pCur->next;
????????????}
????????}
????????return pHead;
????}
};
9.两数相加
题目描述：
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。 示例： 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8 原因：342 + 465 = 807 实现代码：
class Solution {
public: ??? ListNode* addTwoNumbers(ListNode* l1,ListNode* l2) { ??????? ListNode *result = new ListNode(0); ??????? ListNode *temp = result; ??????? int sum = 0; ??????? while(l1||l2) ??????? { ??????????? if(l1) ??????????? { ??????????????? sum = sum + l1->val; ??????????????? l1 = l1->next; ??????????? } ??????????? if(l2) ??????????? { ??????????????? sum = sum + l2->val; ??????????????? l2 = l2->next; ??????????? } ??????????? temp -> next = new ListNode(sum % 10); ??????????? sum = sum/10; ??????????? temp = temp->next; ??????? } ??????? if (sum) ??????????? temp->next = new ListNode(1); ??????? return result->next; ?????? ? ?????? ? ??? } }; 10.删除链表的倒数第N个节点
题目描述：
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例： 给定一个链表: 1->2->3->4->5,和 n = 2. 当删除了倒数第二个节点后，链表变为 1->2->3->5. 说明： 给定的 n 保证是有效的。 进阶： 你能尝试使用一趟扫描实现吗？ 实现代码：
class Solution {
public: ??? ListNode* removeNthFromEnd(ListNode* head,int n) { ??????? ListNode *pre = new ListNode(0); ??????? pre->next = head; ??????? ListNode *p = pre; ??????? ListNode *q = pre; ??????? for(int i = 0; i < n; i++) ??????? { ??????????? p = p->next; ??????? } ??????? while(p->next != NULL) ??????? { ??????????? p = p->next; ??????????? q = q->next; ??????? } ??????? ListNode *k = q->next; ??????? if(k == head) ??????? { ??????????? head = head->next; ??????????? delete k; ??????????? return head; ??????? } ??????? q->next = k->next; ??????? delete k; ??????? return head; ??? } }; 11.合并k个有序链表
题目描述：
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例: 输入: [ ? 1->4->5, ? 1->3->4, ? 2->6 ] 输出: 1->1->2->3->4->4->5->6 实现代码：
class Solution {
public: ??? ListNode* mergeKLists(vector<ListNode*>& lists) { ??????? if (lists.empty()) return NULL; ??????? int n = lists.size(); ??????? while (n > 1) { ??????????? int k = (n + 1) / 2; ??????????? for (int i = 0; i < n / 2; ++i) { ??????????????? lists[i] = mergeTwoLists(lists[i],lists[i + k]); ??????????? } ??????????? n = k; ??????? } ??????? return lists[0]; ??? } ??? ListNode* mergeTwoLists(ListNode* l1,ListNode* l2) { ??????? ListNode *dummy = new ListNode(-1),*cur = dummy; ??????? while (l1 && l2) { ??????????? if (l1->val < l2->val) { ??????????????? cur->next = l1; ??????????????? l1 = l1->next; ??????????? } else { ??????????????? cur->next = l2; ??????????????? l2 = l2->next; ??????????? } ??????????? cur = cur->next; ??????? } ??????? if (l1) cur->next = l1; ??????? if (l2) cur->next = l2; ??????? return dummy->next; ??? } }; 12.两两交换链表中的节点
题目描述：
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。 ? 示例: 给定 1->2->3->4,你应该返回 2->1->4->3. 实现代码：
class Solution {
public: ??? ListNode* swapPairs(ListNode* head) { ??????? if(!head||!head->next) return head;//空链和一个元素的链直接返回 ??????? ListNode* l=head;//定义需要交换的左右节点 ??????? ListNode* r=l->next; ??????? ListNode* p; ??????? l->next=r->next;//交换第一二个节点 ??????? r->next=l; ??????? head=r;//首节点赋值为第二个节点 ??????? p=l;//p赋值为第一对交换成功的右节点 ??????? while(l->next&&l->next->next){//如果剩余节点为0或1则返回head，否则进入循环 ??????????? l=l->next;//转换到下一节点对 ??????????? r=l->next; ??????????? l->next=r->next;//交换节点l，r ??????????? r->next=l; ??????????? p->next=r; ??????????? p=l; ??????? } ??????? return head; ? ??????? } ?????? ? }; 13.旋转链表
题目描述：
给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
示例 1: 输入: 1->2->3->4->5->NULL,k = 2 输出: 4->5->1->2->3->NULL 解释: 向右旋转 1 步: 5->1->2->3->4->NULL 向右旋转 2 步: 4->5->1->2->3->NULL 示例 2: 输入: 0->1->2->NULL,k = 4 输出: 2->0->1->NULL 解释: 向右旋转 1 步: 2->0->1->NULL 向右旋转 2 步: 1->2->0->NULL 向右旋转 3 步: 0->1->2->NULL 向右旋转 4 步: 2->0->1->NULL 实现代码：
class Solution {
public: ??? ListNode* rotateRight(ListNode* head,int k) { ????????? if (!head) return NULL; ????????? int n = 0; ????????? ListNode *cur = head; ????????? while (cur) { ????????????? ++n; ????????????? cur = cur->next; ???????? } ???????? k %= n; ???????? ListNode *fast = head,*slow = head; ???????? for (int i = 0; i < k; ++i) { ???????????? if (fast) fast = fast->next; ???????? } ???????? if (!fast) return head; ???????? while (fast->next) { ???????????? fast = fast->next; ???????????? slow = slow->next; ???????? } ???????? fast->next = head; ???????? fast = slow->next; ???????? slow->next = NULL; ???????? return fast; ??? } }; 14.输出链表中的重复元素
题目描述：
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
示例 1: 输入: 1->1->2 输出: 1->2 示例 2: 输入: 1->1->2->3->3 输出: 1->2->3 实现代码：
class Solution {
public: ??? ListNode* deleteDuplicates(ListNode* head) { ??????? ListNode* cur = head; ??????? while(cur != NULL){ ??????????? ListNode* rear = cur->next; ??????????? if(rear == NULL) ??????????????? return head; ??????????? if(cur->val == rear->val) ??????????????? cur->next = rear->next; ??????????? else ??????????????? cur = cur->next; ??????? } ??????? return head; ??? } }; 15.分隔链表
题目描述：
给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。 示例: 输入: head = 1->4->3->2->5->2,x = 3 输出: 1->2->2->4->3->5 实现代码：
class Solution {
public: ??? ListNode* partition(ListNode* head,int x) { ??????? if(head == NULL) return head; ListNode less_head(0); ??????? ListNode more_head(0); ??????? ListNode* less_ptr = &less_head; ??????? ListNode* more_ptr = &more_head; ??????? ListNode* cur = head; ??????? while(cur != NULL){ ??????????? if(cur->val < x){ ??????????????? less_ptr->next = cur; ??????????????? less_ptr = less_ptr->next; ??????????? } else{ ??????????????? more_ptr->next = cur; ??????????????? more_ptr = more_ptr->next; ??????????? } cur = cur->next; ??????? } ??????? less_ptr->next = more_head.next; ??????? more_ptr->next = NULL; ??????? return less_head.next; ??? } }; 16.反转链表Ⅱ
题目描述：
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明: 1 ≤ m ≤ n ≤ 链表长度。 示例: 输入: 1->2->3->4->5->NULL,m = 2,n = 4 输出: 1->4->3->2->5->NULL 实现代码：
class Solution {
public: ??? ListNode* reverseBetween(ListNode* head,int m,int n) { ??????? if (head == NULL || head->next == NULL) { ??????????? return head; ??????? } ?????? ? ??????? ListNode* dummy = new ListNode(0); ??????? dummy->next = head; ?????? ? ??????? ListNode* prev = dummy; ??????? for (int i = 0; i < m - 1; i++) { ??????????? prev = prev->next; ??????? } ??????? ListNode* start = prev->next; ??????? ListNode* then = start->next; ?????? ? ??????? for (int i = 0; i < n - m; i++) { ??????????? start->next = then->next; ??????????? then->next = prev->next; ??????????? prev->next = then; ??????????? then = start->next; ??????? } ?????? ? ??????? return dummy->next; ??? } }; 17.环形链表
题目描述：
给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。 实现代码：
class Solution {
public: ??? bool hasCycle(ListNode *head) { ??????? ListNode *L1,*L2; ??????? L1=head; ??????? L2=head; ??????? while(L1!=NULL && L2 != NULL && L1->next != NULL) ??????? { ??????????? L1 = L1->next->next; ??????????? L2 = L2->next; ??????????? if(L1 == L2) ??????????????? return true; ??????? } ??????? return false; ??? } }; 18.移除链表元素
题目描述：
删除链表中等于给定值 val 的所有节点。
示例: 输入: 1->2->6->3->4->5->6,val = 6 输出: 1->2->3->4->5 实现代码：
class Solution {
public: ??? ListNode* removeElements(ListNode* head,int val) { while ((head!=NULL)&&(head->val == val)) ?? ?{ ?? ??? ?head = head->next; ?? ?} ?? ?ListNode* pCurrent = head; ??? if (pCurrent == NULL) return NULL; ?? ?while (pCurrent->next!=NULL) ?? ?{ ?? ??? ?if (pCurrent->next->val == val) ?? ??? ?{ ?? ??? ??? ?pCurrent->next = pCurrent->next->next; ?? ??? ?} ?? ??? ?else ??????????? pCurrent = pCurrent->next; ?? ?} ?? ?return head; ??? } }; 19.回文链表
题目描述：
请判断一个链表是否为回文链表。
示例 1: 输入: 1->2 输出: false 示例 2: 输入: 1->2->2->1 输出: true
实现代码：
class Solution {
public: ??? bool isPalindrome(ListNode* head) { ??????????????? int n=len(head); ??????? if(n==1)return true; ??????? ListNode*head2=head; ??????? for(int i=0;i<(n/2+n%2);i++){ ??????????? head2=head2->next; ??????? } ??????? head2=reverseList(head2); ??????? while(head2!=NULL){ ??????????? if(head->val!=head2->val) return false; ??????????? else{head=head->next;head2=head2->next;} ??????? } ??????? return true; ??? } ??? int len(ListNode*head){ ??????? int n=0; ??????? while(head!=NULL){ ??????????? head=head->next; ??????????? ++n; ??????? } ??????? return n; ??? } ??? ListNode* reverseList(ListNode* head) { ??????? ListNode*pt=head; ??????? ListNode*temp; ??????? if(pt==NULL) return head; ??????? while(pt->next!=NULL){ ??????????? temp=pt->next; ??????????? pt->next=pt->next->next; ??????????? temp->next=head; ??????????? head=temp; ??????? } ??????? return head; ??? } }; 20.链表的中间节点
题目描述：
给定一个带有头结点 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。 ? 示例 1： 输入：[1,2,3,4,5] 输出：此列表中的结点 3 (序列化形式：[3,5]) 返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,5])。 注意，我们返回了一个 ListNode 类型的对象 ans，这样： ans.val = 3,ans.next.val = 4,ans.next.next.val = 5,以及 ans.next.next.next = NULL. 示例 2： 输入：[1,5,6] 输出：此列表中的结点 4 (序列化形式：[4,6]) 由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。 实现代码：
class Solution { public: ??? ListNode* middleNode(ListNode* head) { ??????? ListNode*cur=head->next; ??????? ListNode*prev=head; ??????? while(cur) { ??????????? if(cur->next) { ??????????????? cur=cur->next->next; ??????????? } else { ??????????????? cur=cur->next; ??????????? } prev=prev->next; ??????? } ??????? return prev; ??? } };
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |