day8-链表

1、反转链表

1. 描述

   给你单链表的头节点 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进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
   

2. 思路

   指针分别指向前中后三个node，将next指向pre结点

3. 代码

   #include 
   using namespace std;
   #include 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* reverseList(ListNode* head) {ListNode *pre;ListNode *cur;ListNode *nxt;if(!head || !head->next)     return head;cur = head->next;pre = head;head->next = nullptr;while(cur) {nxt = cur->next;// if(!nxt)    printf("nxt: %d  ",nxt->val);if(!cur)printf("pre: %d   cur:  %d\n",pre->val,cur->val);cur->next = pre;pre = cur;cur = nxt;if(!cur&&!pre)printf("==>>pre: %d   cur:  %d\n",pre->val,cur->val);}head = pre;return head;}
   };int main() {ListNode *head = new ListNode;ListNode *p;p = head;vector num = {};for(int i = 0; i < num.size(); i++) {ListNode *tmp = new ListNode(num[i]);head->next = tmp;head = head->next;}Solution sol;p = sol.reverseList(p->next);while (p){printf("%d  ->  ",p->val);p = p->next;}printf("\n");return 0;
   }
   

2、删除排序列表的重复元素

1. 描述

   给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。示例 1：
   输入：head = [1,1,2]
   输出：[1,2]
   示例 2：
   输入：head = [1,1,2,3,3]
   输出：[1,2,3]提示：
   链表中节点数目在范围 [0, 300] 内
   -100 <= Node.val <= 100
   题目数据保证链表已经按升序 排列
   

2. 思路

   当前结点与下个结点比较，相同则删，不同则遍历下一个

3. 代码

   #include 
   using namespace std;
   #include 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* deleteDuplicates(ListNode* head) {ListNode *cur;ListNode *nxt;if(!head || !head->next)    return head;cur = head;nxt = head->next;while (cur && cur->next) {if(cur->val == nxt->val) {ListNode *tmp;tmp = nxt;nxt = nxt->next;tmp->next = nullptr;delete tmp;cur->next = nxt;} else {cur = nxt;nxt = nxt->next;}}return head;}
   };int main() {ListNode *head = new ListNode;ListNode *p;p = head;vector num = {1,1,2,3,3};for(int i = 0; i < num.size(); i++) {ListNode *tmp = new ListNode(num[i]);p->next = tmp;p = p->next;}Solution sol;p = sol.deleteDuplicates(head->next);while (p){printf("%d  -->  ",p->val);p = p->next;}printf("\n");    return 0;
   }