代码随想录算法训练营第四天 | 24. 两两交换链表中的节点 | 19. 删除链表的倒数第 N 个结点 | 面试题 02.07. 链表相交
24. 两两交换链表中的节点
题意
题目链接
将链表节点两两交换
解
struct ListNode* swapPairs(struct ListNode* head) {
struct ListNode *tmp = NULL, *cur = NULL;
int a;
cur = head;
while (cur != NULL && cur->next != NULL) {
tmp = cur->next;
a = cur->val;
cur->val = tmp->val;
tmp->val = a;
cur = tmp->next;
}
return head;
}
19. 删除链表的倒数第 N 个结点
题意
删除链表的倒数第 N 个结点
解
一次遍历删除, 用到双指针. 因为要删除指定的节点, 所以要找到删除节点的前一个节点, 所以这个指针区间就被放大了1个, 所以用了虚节点, 将原来的链表长度扩大1, 就不需要判断边界条件了(比如链表长度为2, 要删除倒数第二个)
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
int i = 0;
struct ListNode *slow = NULL, *fast = NULL, *tmp = NULL, *new = NULL;
new = (struct ListNode *)malloc(sizeof(struct ListNode));
new->next = head;
slow = fast = new;
for (i = 0; i < n; i++) {
fast = fast->next;
}
while (fast->next != NULL) {
slow = slow->next;
fast = fast->next;
}
tmp = slow->next;
slow->next = slow->next->next;
free(tmp);
head = new->next;
free(new);
return head;
}
面试题 02.07. 链表相交
题意
找到两个链表的相交位置, 也就是说两个链表用了相同内存节点
解
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
struct ListNode *cura = NULL, *curb = NULL;
int lena = 0, lenb = 0;
cura = headA, curb = headB;
while (cura != NULL) {
lena++;
cura = cura->next;
}
while (curb != NULL) {
lenb++;
curb = curb->next;
}
cura = headA;
curb = headB;
if (lena < lenb) {
cura = headB;
curb = headA;
int tmp = lena;
lena = lenb;
lenb = tmp;
}
while (lena-- - lenb > 0) {
cura = cura->next;
}
while (cura != NULL) {
if (cura == curb) {
return cura;
}
cura = cura->next;
curb = curb->next;
}
return NULL;
}
142. 环形链表 II
题意
如果链表中存在一个环, 则返回这个环的入口
解
方法1
一开始想的是有环, 表示有两个节点的next都会指向同一个节点, 想法如下
/* 两个节点的next都指向同一个节点时, 这个被指向的节点就是环的入口
* 需要考虑整个都是环的情况, 所以使用虚节点
*/
不太好实现
方法2
快慢指针相遇
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode *slow = NULL, *fast = NULL;
int flag = 0;
slow = fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
flag = 1;
break;
}
}
if (flag == 0) return NULL;
fast = head;// 从头开始时, 找环的入口
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return fast;
}
原文地址:https://blog.csdn.net/geshifansheng_7/article/details/138034299
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!