【数据结构】面试OJ题——链表

 

目录

1.移除链表元素

思路：

 2.反转链表

思路：

3.链表的中间结点

思路：

 4.链表中的倒数第K个结点

 思路：

 5.合并两个有序链表

 思路：

 6.链表分割

思路：

7.链表的回文结构

思路：

 8.随机链表的复制

 思路：

---

1.移除链表元素

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

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

思路：

 定义新链表的头结点和尾结点，循环遍历原链表即可，遇到复合的结点删除即可；

最后将尾结点的next置空。

因为这里并没有使用哨兵位，所以第一次插入的时候，要特殊处理

struct ListNode* removeElements(struct ListNode* head, int val) {struct ListNode* newnode = NULL,*tail = NULL;struct ListNode* cur = head;while(cur){//if(cur->val != val){//空，尾插if(tail == NULL){newnode = tail = cur;}else{tail->next = cur;tail = tail->next;}cur = cur->next;}else{struct ListNode* tmp = cur;cur = cur->next;free(tmp);tmp = NULL;}}if(tail)tail->next = NULL;return newnode;
}

 2.反转链表

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

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

思路：

 定义三指针，当前位置，上一个位置，下一个位置；

将结点next链接到上一个结点即可，然后将下一个位置赋给当前指针；

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

3.链表的中间结点

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

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

 

思路：

使用快慢指针方式，快指针走两步，慢指针走一步，可以发现当快指针为NULL  或者快指针的下一个为空的时候 slow是中间结点 

struct ListNode* middleNode(struct ListNode* head) {struct ListNode* fast = head;struct ListNode* slow = head;while(fast && fast->next){//快指针走两步，慢指针走一步fast = fast->next->next;slow = slow->next;}return slow;
}

 4.链表中的倒数第K个结点

链表中倒数第k个结点_牛客题霸_牛客网 (nowcoder.com)

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

 思路：

一般链表问题，使用最多的解决方式就是快慢指针，这个题目和第三题相似很多；

先让快指针走K步，然后两指针同时走；

注：这里的快指针和慢指针一起走 是一步步走；同时，防止快指针走K步越界了，

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {//快慢指针struct ListNode* fast = pListHead;struct ListNode* slow = pListHead;//快指针先走k步while(k--){if(fast == NULL)return NULL;fast = fast->next;}//同时走while(fast){fast = fast->next;slow = slow->next;}return slow;
}

 5.合并两个有序链表

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

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

 思路：

合并两个链表按照大小顺序排列，尾插小的结点；

第一次：将走完链表其中一条，注意并没有定义哨兵位，所以第一次插入特殊处理

第二次：将没走完的链表直接尾插到新链表后即可；

将小的结点尾插到新链表中

 

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {struct ListNode* newnode = NULL,*tail = NULL;if(list1 == NULL)return list2;if(list2 == NULL)return list1;while(list1 && list2){if(list1->val < list2->val){if(newnode == NULL){newnode = tail = list1;}else{tail->next = list1;tail = tail->next;}list1 = list1->next;}//list2else{if(newnode == NULL){newnode = tail = list2;}else{tail->next = list2;tail = tail->next;}list2 = list2->next;}}if(list1)tail->next = list1;if(list2)tail->next = list2;return newnode;
}

 6.链表分割

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

现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

 

思路：

对于链表分割最好用带头哨兵位的链表来解决，减化了两条链表的链接问题；如果不用哨兵位，要增加很多特殊处理判断；

有了哨兵位，在链接两条链表时，直接链接即可，尾部置NULL；

 ListNode* partition(ListNode* phead, int x) {struct ListNode* cur = phead;struct ListNode* list1,*tail1,*list2,*tail2;//哨兵位list1 = tail1= (struct ListNode*)malloc(sizeof(struct ListNode));list2 = tail2= (struct ListNode*)malloc(sizeof(struct ListNode));while(cur){if(cur->val < x)    //小于x{tail1->next = cur;tail1 = tail1->next;}else    //大于等于x{tail2->next = cur;tail2 = tail2->next;}cur = cur->next;}tail1->next = list2->next;   //链接两条链表tail2->next = NULL;  //尾部置NULLphead = list1->next;free(list1);free(list2);return phead;}

7.链表的回文结构

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

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。

给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

思路：

1.先用快慢指针找到中间结点

2.反转中间节点后的链表

3.是否为回文判断

 bool chkPalindrome(ListNode* head) {//快慢指针找到中间节点struct ListNode* slow = head,*fast = head;while(fast && fast->next){fast = fast->next->next;slow = slow->next;}//此刻slow 是中间节点//反转mid后的链表struct ListNode* mid = slow;   struct ListNode* cur = mid;struct ListNode* newnode = NULL;while(cur){struct ListNode* next = cur->next;cur->next = newnode;newnode = cur;cur = next;}//回文比较struct ListNode* phead = head;while(phead && newnode){if(phead->val != newnode->val)return false;phead = phead->next;newnode = newnode->next;}return true;}

 8.随机链表的复制

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

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

 

 思路：

1.先复制一条没有random的新链表，每个节点尾插到对应结点后面

2.添加random，可以发现，复制的结点的上一个结点的random就是该结点需要的random

3.将添加后的链表尾插到新链表中，记得跳过原链表的结点

 

 

struct Node* copyRandomList(struct Node* head) {struct Node* cur = head;while(cur){struct Node* newnode = (struct Node*)malloc(sizeof(struct Node));newnode->val = cur->val;newnode->next = cur->next;cur->next = newnode;cur = cur->next->next;}//添加randomcur = head;while(cur){struct Node* copy =cur->next;//原链表 random为空情况if(cur->random == NULL){copy->random = NULL;}else{copy->random = cur->random->next;}cur = cur->next->next;}//尾插cur = head;struct Node* newnode = NULL,*tail = NULL;while(cur){struct Node* copy =cur->next;struct Node* next = copy->next;;if(tail == NULL){newnode = tail = copy;}else{tail->next = copy;tail = tail->next;}cur->next = next;cur = next;}return newnode;
}