【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]

提示：

• 链表中结点的数目为 sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= 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 3

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