【算法集训】基础数据结构:三、链表
链表就是将所有数据都用一个链子串起来,其中链表也有多种形式,包含单向链表、双向链表等;
现在毕竟还是基础阶段,就先学习单链表吧;
链表用头结点head
表示一整个链表,每个链表的节点包含当前节点的值val
和下一个节点next
。
链表的好处就是删除和插入比较容易,不需要移动其他元素。只需要改变下一个节点的指向值即可。
第一题 面试题 02.02. 返回倒数第 k 个节点
https://leetcode.cn/problems/kth-node-from-end-of-list-lcci/description/
返回第k个节点的值,这里使用双指针的思路,定义一个快指针和慢指针,两个指针之间间隔k位,快指针移动到最后一个节点的下一个节点(即节点为空时)时就停止,此时慢指针对应的就是倒数第k个节点值。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
int kthToLast(struct ListNode* head, int k){
struct ListNode * fast = head;
struct ListNode * slow = head;
for(int i = 0; i < k; ++i) {
fast = fast->next;
}
while(fast) {
fast = fast->next;
slow = slow->next;
}
return slow->val;
}
第二题 19. 删除链表的倒数第 N 个结点
https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/
删除倒数第n
个节点,思路和上一题一样,先找到倒数第N个节点,我们要删除这个节点,所以需要找到这个节点的前一个节点N+1
;
直接将下一个值指向N的下一个值即可。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
struct ListNode * fast = head;
struct ListNode * slow = head;
for(int i = 0; i < n; ++i) {
fast = fast->next;
if(fast == NULL) {
return head->next;
}
}
fast = fast->next;
while(fast) {
fast = fast->next;
slow = slow->next;
}
slow->next = slow->next->next;
return head;
}
第三题 206. 反转链表
https://leetcode.cn/problems/reverse-linked-list/description/
第一种:迭代方法,定义一个当前节点cur和前一个节点pre,遍历链表,将指向换一下方向即可,注意保存cur->next
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode * pre = NULL;
struct ListNode * cur = head;
while(cur) {
struct ListNode * temp = cur->next;
cur->next = pre;
pre = cur;
cur = temp;
}
return pre;
}
第二种:递归
主要思想就是从最后一个开始,将它的指针指向前一个节点,然后前一个节点指向NULL;
这时又递归到前一个节点,和上面操作一样,一直到第一个头结点,这时头结点会置为NULL;
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode * doReverse(struct ListNode * head, struct ListNode ** outHead) {
递归临界点,如果到最后一个节点则开始往回走;
if(head == NULL || head->next == NULL) {
*outHead = head; outhead是最终翻转后的头结点,所以这里head最后一个节点就是outhead的头结点
return head;
}
每次递归都向下一层,返回值为反转后的
struct ListNode * tail = doReverse(head->next, outHead);
tail->next = head;
head->next = NULL;
return head;
}
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode * outHead;
doReverse(head, &outHead);
return outHead;
}
第四题 237. 删除链表中的节点
https://leetcode.cn/problems/delete-node-in-a-linked-list/description/
这道题代码不难,主要的是思想,能不能想到这样的方法。
只给了一个需要删除的节点node
,让你删除这个节点。
那么我们只需要将node->next
的值赋值给node
,那么这样就可以删除node->next
,这样同样可以达到需要的结果。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
void deleteNode(struct ListNode* node) {
node->val = node->next->val;
node->next = node->next->next;
}
第五题 24. 两两交换链表中的节点
https://leetcode.cn/problems/swap-nodes-in-pairs/description/
本题有两种做法,迭代和递归,递归相对来说难理解。
一、递归
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* swapPairs(struct ListNode* head) {
定义临界点,即递到最后一个节点或者空时开始归。
if(head == NULL || head->next == NULL) {
return head;
}
这里就是记录递归的当前节点和下一个节点,用于后续交换
struct ListNode* now = head;
struct ListNode* next = head->next;
这里记录的是后面已经完成交换的头结点nextnext;
struct ListNode* nextnext = swapPairs(now->next->next);
这里算是核心,
now->next = nextnext; 每次将当前节点的下个节点指向已经完成交换的头结点
next->next = now; 将当前节点下一个节点又指向当前节点,即完成本轮交换
return next;
}
二、迭代
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode * virhead = new ListNode();
virhead->next = head;
ListNode * cur = virhead;
while (cur->next != nullptr && cur->next->next != nullptr) {
ListNode * temp1 = cur->next;
ListNode * temp2 = cur->next->next->next;
cur->next = cur->next->next;
cur->next->next = temp1;
cur->next->next->next = temp2;
cur = cur->next->next;
}
return virhead->next;
}
};
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!