【day1】数据结构刷题 链表
一 反转链表
206. 反转链表
给你单链表的头节点
head，请你反转链表，并返回反转后的链表。示例 1：
输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]示例 2：
输入：head = [1,2] 输出：[2,1]示例 3：
输入：head = [] 输出：[]提示：
- 链表中节点的数目范围是
[0, 5000]-5000 <= Node.val <= 5000进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
解答
分析，我们要反转链表，这个时候我们需要三个指针，prev，next，current
这里就是不断地进行反转，移动这个current，prev 和 next进行反转
current对当前的节点进行操作，next为current移动用，prev是用来current进行指向的/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* reverseList(struct ListNode* head) { struct ListNode* Prev = NULL; struct ListNode* Next = NULL; struct ListNode* current = head; while(current != NULL){ Next = current -> next; current -> next = Prev; Prev = current; current = Next; } head = Prev; return head; }这里要注意要先把prev进行指向current才可以将current指向Next
然后最后current是到达NULL的，我们只需要把这个头指针指向prev就好了
二 合并两个链表
给你单链表的头节点
head，请你反转链表，并返回反转后的链表。示例 1：
输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]示例 2：
输入：head = [1,2] 输出：[2,1]示例 3：
输入：head = [] 输出：[]提示：
- 链表中节点的数目范围是
[0, 5000]-5000 <= Node.val <= 5000进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
这里我们首先要找到合并两个链表之后的头指针指向哪个地方
所以我们第一步就是把头指针确认好，只需要比较一下链表头的元素的大小就好了，然后对应的List也要移动一格子，是为了比较是这个链表的值小还是另外一个
然后就是利用一个尾指针，来进行不断的合并
题目里面的List1和List2向后移动
最后有剩下的话就直接赋到新链表的后面就好了/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { if (list1 == NULL) return list2; if (list2 == NULL) return list1; struct ListNode* head = NULL; struct ListNode* tail = NULL; if (list1->val <= list2->val) { head = list1; list1 = list1->next; } else { head = list2; list2 = list2->next; } tail = head; while (list1 != NULL && list2 != NULL) { if (list1->val <= list2->val) { tail->next = list1; list1 = list1->next; } else { tail->next = list2; list2 = list2->next; } tail = tail->next; } if (list1 != NULL) { tail->next = list1; } else { tail->next = list2; } return head; }
三 删除倒数第N个节点
给你一个链表，删除链表的倒数第
n个结点，并且返回链表的头结点。示例 1：
输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]示例 2：
输入：head = [1], n = 1 输出：[]示例 3：
输入：head = [1,2], n = 1 输出：[1]提示：
- 链表中结点的数目为
sz1 <= sz <= 300 <= Node.val <= 1001 <= n <= sz进阶：你能尝试使用一趟扫描实现吗？
这个首先我要先让一个指针进行移动，然后这个时候就移动到倒是的N+1的位置
如果这个时候已经是NULL的话，那么就是删除头节点，我是让这个指针移动n的
然后再让另外一个指针进行移动，移动到N+1位置
为什么这样子操作？
我们要移动到倒是第n个操作，那么我正序来看，首先我移动到第n个位置，然后再让一个指针跟着我另外一个指针移动，当第一个指针指向了NULL，那么不就是到n+1的位置嘛/** * 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 = 1; i <= n; i++){ fast = fast->next; } //如果是NULL的话，那么就是头节点了 if(fast == NULL){ struct ListNode* temp = head; head = head -> next; free(temp); return head; } while(fast->next != NULL){ fast = fast -> next; slow = slow -> next; } struct ListNode* temp1 = slow->next; slow->next = slow->next->next; free(temp1); return head; }为什么删除头节点
如果链表长度为
n，那么倒数第n个节点就是头节点。
例如，链表为
[1, 2, 3]，n = 3：
倒数第 1 个节点是
3。倒数第 2 个节点是
2。倒数第 3 个节点是
1（头节点）。
四 删除元素非递减的单链表中的重复元素
L是一个带头结点的单链表，其结点存储的数据是非递减有序的。函数RemoveDuplicate要将L中重复元素去除，每组重复元素只留下其中一个。返回删除重复元素后的链表头指针。。
函数接口定义：
List RemoveDuplicate( List L );其中List结构定义如下：
typedef struct Node *PtrToNode; struct Node { ElementType Data; /* 存储结点数据 */ PtrToNode Next; /* 指向下一个结点的指针 */ }; typedef PtrToNode List; /* 定义单链表类型 */L是一个带头结点的单链表，其结点存储的数据是非递减有序的；
裁判测试程序样例：
#include <stdio.h> #include <stdlib.h> typedef int ElementType; typedef struct Node *PtrToNode; struct Node { ElementType Data; PtrToNode Next; }; typedef PtrToNode List; List Read(); /* 细节在此不表 */ void Print( List L ); /* 细节在此不表；空链表将输出NULL */ List RemoveDuplicate( List L ); int main() { List L; L = Read(); L = RemoveDuplicate(L); Print(L); return 0; } /* 你的代码将被嵌在这里 */4 1 2 2 31 2 3
这里就是不断地记录前面一个然后跟后面进行对比就好了
List RemoveDuplicate(List L){ List temp = L->next; List prev = NULL; while(temp->next != NULL){ prev = temp; temp = temp -> next; if(prev -> Data == temp -> Data){ List temp1 =temp; prev -> Next = temp ->Next; temp = temp -> Next; free(temp1); } } return L; }