【数据结构初阶】单链表面试题|内含链表带环问题

目录

前言

链表面试题 

1. 删除链表中等于给定值 val 的所有节点。oj链接

2.反转一个单链表。oj链接

3. 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。oj链接

 4. 输入一个链表，输出该链表中倒数第k个结点。oj链接

5. 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 oj链接

6. 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。oj链接

7. 链表的回文结构。 oj链接

8. 输入两个链表，找出它们的第一个公共结点。 oj链接

9. 给定一个链表，判断链表中是否有环。 oj链接

10. 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL。 oj链接

 总结

---

前言

上篇文章学习了单链表的原理以及实现，这节课我们来做几道链表的oj题来练练手吧。

---

链表面试题 

1. 删除链表中等于给定值 val 的所有节点。oj链接

我们对链表进行遍历，保存上一个结点prev，如果不等于val，那就不进行操作，如果等于val，我们就直接将prev的next指向当前位置的next，堆该结点进行删除。

struct ListNode* removeElements(struct ListNode* head, int val){struct ListNode* prve=head,*cur=head;while(cur){if(cur->val==val){if(cur==head){head=cur->next;cur=cur->next;}else{prve->next=cur->next;cur=cur->next;}}else{prve=cur;cur=cur->next;}}return head;
}

2.反转一个单链表。oj链接

 

 我们使用三指针法，使用cur保存当前结点，使用next保存当前结点的next，每次只需将cur的next指向newhead即可。

struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* cur=head;struct ListNode* newhead=NULL;while(cur){struct ListNode* next=cur->next;cur->next=newhead;newhead=cur;cur=next;}return newhead;
}

3. 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。oj链接

 

 快指针一次走两步，慢指针一次走一步，当快指针走到空或快指针的next走到空时，此时慢指针就这中间结点处。

struct ListNode* middleNode(struct ListNode* head){struct ListNode* fast,*slow;slow=fast=head;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;}return slow;
}

 4. 输入一个链表，输出该链表中倒数第k个结点。oj链接

 这道题还可以通过快慢指针来解决，快指针先走k步，然后慢指针和快指针一块走，当快指针指向空时，慢指针就到了倒数第k个位置。

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {struct ListNode* fast,*slow;fast=slow=pListHead;while(k--){if(!fast)return NULL;elsefast=fast->next;}while(fast){fast=fast->next;slow=slow->next;}return slow;
}

5. 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 oj链接

 这里我们使用归并的思想，比较两个链表的值，小的插入新的链表。

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){struct ListNode* head=NULL;struct ListNode* cur=NULL;if(!list1)return list2;if(!list2)return list1;while(list1&&list2){if(list1->val > list2->val){if(head==NULL)cur=head=list2;else{cur->next=list2;cur=list2;}list2=list2->next;}else{if(head==NULL)cur=head=list1;else{cur->next=list1;cur=list1;}list1=list1->next;}}if(list1)cur->next=list1;if(list2)cur->next=list2;return head;
}

6. 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。oj链接

开两个带哨兵位的结点，分别插入大于x的数和小于x的数，大于x尾插到greatTail，小于x插入lessTail，最终将两个链表连起来。

class Partition {public:struct ListNode* partition(struct ListNode* head, int x) {struct ListNode* lessHead, * lessTail, * greaterHead, *greaterTail;struct ListNode* cur = head;lessHead = lessTail = (struct ListNode*)malloc(sizeof(struct ListNode));lessHead->next=NULL;greaterHead = greaterTail = (struct ListNode*)malloc(sizeof(struct ListNode));greaterHead->next = NULL;while (cur) {if (cur->val < x) {lessTail->next = cur;lessTail = cur;} else {greaterTail->next = cur;greaterTail = cur;}cur = cur->next;}lessTail->next = greaterHead->next;greaterTail->next = NULL;struct ListNode* newnode = lessHead->next;free(lessHead);free(greaterHead);return newnode;}
};

7. 链表的回文结构。 oj链接

 可以找到链表的中间结点，然后将中间结点后边逆置，当前边与后边相同时，说明是回文结构。

struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* cur=head;struct ListNode* newhead=NULL;while(cur){struct ListNode* next=cur->next;cur->next=newhead;newhead=cur;cur=next;}return newhead;
}
class PalindromeList {
public:bool chkPalindrome(ListNode* A) {struct ListNode* fast,* slow;fast=slow=A;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;}ListNode* newHead=slow;struct ListNode* B= reverseList(slow);while(B->next&&A->next){if(A->val!=B->val){return false;}else {A=A->next;B=B->next;}}return true;}
};

8. 输入两个链表，找出它们的第一个公共结点。 oj链接

 判断是否有公共结点只需要判断两个链表的最后一个结点是否相同，而要找到第一个相遇结点时，我们可以使两个链表同时走，第一个相等的结点就是第一个公共结点。

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode* curA=headA;struct ListNode* curB=headB;int lenA=1;int lenB=1;while(curA->next){curA=curA->next;lenA++;}while(curB->next){curB=curB->next;lenB++;}if(curA!=curB)return NULL;int num=abs(lenA-lenB);struct ListNode *longlist=headA;struct ListNode *shortlist=headB;if(lenA<lenB){longlist=headB;shortlist=headA;}while(num--){longlist=longlist->next;}while(longlist!=shortlist){longlist=longlist->next;shortlist=shortlist->next;}return longlist;
}

9. 给定一个链表，判断链表中是否有环。 oj链接

 我们可以通过使用快慢指针，快指针每次走两步，慢指针每次走一步，他们如果相遇那么说明这个链表是带环的，下边附上我的手写证明。

 

bool hasCycle(struct ListNode *head) {struct ListNode*fast,*slow;fast=slow=head;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;if(slow==fast)return true;}return false;
}

10. 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL。 oj链接

附上手写证明 

 

struct ListNode *detectCycle(struct ListNode *head) {struct ListNode*fast,*slow,*meet;fast=slow=head;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;if(slow==fast){meet=slow;while(head!=meet){head=head->next;meet=meet->next;}return meet;}}return NULL;
}

 总结

今天我们讲解了十道链表面试题，希望可以帮到大家。