数据结构学习——链表面试题

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

203. 移除链表元素 - 力扣（LeetCode）

方法一：

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

在这里插入图片描述

方法二：

哨兵位的头节点不存储有效数据

struct ListNode* removeElements(struct ListNode* head, int val) 
{struct ListNode* newhead = NULL,*tail=NULL;struct ListNode* cur=head;//哨兵位newhead =tail=(struct ListNode*)malloc(sizeof(struct ListNode));while(cur){//不是val的节点拿下来尾插if(cur->val !=val){tail->next=cur;tail=tail->next;cur=cur->next;}else {struct LIstNode* tmp= cur;cur=cur->next;free(tmp);}}tail->next =NULL;struct ListNode* tmp  =newhead;newhead=newhead->next;free(tmp);return newhead;
}

2.反转一个单链表。

206. 反转链表 - 力扣（LeetCode）

struct ListNode* reverseList(struct ListNode* head) 
{if(head==NULL)retuen NULL;struct ListNode* n1 ,*n2.n3;n1 = NULL;n2 = head;n3 = head->next;while(n2){n2->next=n1;n1=n2;n2=n3if(n3)n3=n3->next;}return n1;
}

在这里插入图片描述

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

876. 链表的中间结点 - 力扣（LeetCode）

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

在这里插入图片描述

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

面试题 02.02. 返回倒数第 k 个节点 - 力扣（LeetCode）

int kthToLast(struct ListNode* head, int k)
{struct ListNode*cur=head;while(cur){if(cur->val==k){return cur->val;}cur=cur->next;}return NULL;
}

在这里插入图片描述

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

21. 合并两个有序链表 - 力扣（LeetCode）

typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
{if(list1==NULL)return list2;if(list2==NULL)return list1;ListNode* phead1 ,*phead2 ;ListNode* phead3 ,*cur;phead3 = cur = (ListNode*)malloc(sizeof(ListNode));phead1 = list1; phead2 = list2;while(phead1 && phead2){if(phead1->val <= phead2->val){cur->next = phead1;phead1 = phead1->next;}else{cur->next = phead2;phead2 = phead2->next;}cur = cur->next;}if(phead1){cur->next = phead1;}if(phead2){cur->next = phead2;}phead1 = phead3->next;free(phead3);return phead1;
}

在这里插入图片描述

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

链表分割_牛客题霸_牛客网 (nowcoder.com)

class Partition {
public:ListNode* partition(ListNode* pHead, int x) {// write code herestruct ListNode *head1,*tail1,*head2,*tail2;head1 = tail1 = (struct ListNode*) malloc(sizeof(struct ListNode));head2 = tail2 = (struct ListNode*) malloc(sizeof(struct ListNode));struct ListNode *cur = pHead;while(cur){if(cur->val <x){tail1->next = cur;tail1 = tail1->next;}else{tail2->next = cur;tail2 = tail2->next;}cur=cur->next;}tail1->next = head2->next;tail2->next = NULL;pHead = head1->next;free(head1);free(head2);return pHead;}
};

在这里插入图片描述

7. 链表的回文结构。

链表的回文结构_牛客题霸_牛客网 (nowcoder.com)

class PalindromeList {
public:struct ListNode* reverseList(struct ListNode* head) 
{if(head == NULL)return NULL;struct ListNode* n1 ,*n2,*n3;n1 = NULL;n2 = head;n3 = head->next;while(n2){n2->next=n1;n1=n2;n2=n3;if(n3)n3=n3->next;}return n1;
}struct ListNode* middleNode(struct ListNode* head)
{struct ListNode*prev=head,*tail=head;while(tail && tail->next){prev=prev->next;tail=tail->next->next;}return prev;
}bool chkPalindrome(ListNode* head) {// write code herestruct ListNode* mid = middleNode(head);struct ListNode* rhead = reverseList(head); while(head && rhead){if(head->val != rhead->val){return false;}head = head->next;rhead = rhead ->next;}return true;}};

思路：先找中间，再逆置，然后比较

在这里插入图片描述

8. 环形链表I

141. 环形链表 - 力扣（LeetCode）

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

在这里插入图片描述

9.环形链表II

142. 环形链表 II - 力扣（LeetCode）

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode *detectCycle(struct ListNode *head) 
{struct ListNode * slow=head,*fast=head;while(fast && fast->next){slow=slow->next;fast=fast->next->next;if(fast==slow){struct ListNode * meet = slow;while(head!=meet){head=head->next;meet=meet->next;}return meet;}}return NULL;
}

在这里插入图片描述

10. 链表复制

138. 随机链表的复制 - 力扣（LeetCode）

struct Node* copyRandomList(struct Node* head) 
{struct Node* cur=head;while(cur){struct Node* copy=(struct Node*)malloc(sizeof(struct Node));copy->val = cur->val;copy->next = cur->next;cur->next = copy;cur = copy->next;}cur = head;while(cur){struct Node* copy = cur->next;if(cur->random == NULL){copy->random = NULL;}else{copy->random = cur->random->next;}cur = copy->next;}struct Node*newhead=NULL,*tail = NULL;cur = head;while(cur){struct Node* copy = cur->next;struct Node* next = copy->next;if(tail == NULL){newhead = tail =copy;}else{tail->next = copy;tail = tail->next;}cur->next = next;cur=next;}return newhead;
}

在这里插入图片描述

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

160. 相交链表 - 力扣（LeetCode）

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

在这里插入图片描述