【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; }