203. 移除链表元素
题目描述
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
示例 1：
输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5]
示例 2：
输入：head = [], val = 1 输出：[]
示例 3：
输入：head = [7,7,7,7], val = 7 输出：[]
思路分析
双指针
先为原始链表创建一个虚拟头结点(便于操作),然后定义两个指针,pre指向前一个节点,cur指向当前节点.
当前节点满足条件,则进行移除操作.
最后删除创建的虚拟头结点.
图解过程:
参考代码
#include<bits/stdc++.h> using namespace std; 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(nullptr) {} }; //采用双指针 ListNode* removeElements(ListNode* node, int val) { ListNode* head = new ListNode(-1,node) ;//定义头结点 ListNode* pre = head;//初始化 ListNode* cur = head->next;//这里也可以直接使用一个cur变量来删除节点,我们定义两个,逻辑更加清晰 ListNode* temp; while(cur!=NULL) { if(cur->val==val) { temp = cur; pre->next = cur->next; cur = cur->next; delete temp; } else { pre = cur; cur = cur->next; } } //删除虚拟头结点 temp = head->next; delete head; return temp; }
206. 反转链表
题目描述
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2] 输出：[2,1]
示例 3：
输入：head = [] 输出：[]
思路分析
方法一：双指针
基本思路:从前往后将指针的方向改变,返回最后一个节点
使用pre指向前一个节点,cur代表当前节点,从第一个节点开始进行遍历,每次让cur指向pre,之后cur继续遍历下一个节点,直至链表遍历完毕.
方法二：递归（从前往后改变指针方向）
思路和方法一基本一致,递归实际上就是自己调用自己,每次的操作一致.
每次我们需要改变指针指向,需要操作两个节点,当前节点cur和上一个节点pre,所以这就是递归函数的参数.
递归的结束条件就是当前节点为NULL,则不再需要改变方向了.递归结束.
方法三：递归（从后往前改变指针方向）
参考代码
方法一：双指针
//方法一:双指针法 ListNode* reverseList(ListNode* head) { if(head==NULL||head->next==NULL) { //判断0个和1个节点情况,不用进行反转 return head; } ListNode *pre = NULL,*cur = head,*temp = head->next; //开始 从前往后改变指针的指向 while(cur) { temp = cur->next;//保存下一个节点 cur->next = pre;//改变指向 pre = cur;//pre后移动 cur = temp; //cur后移动 } return pre; }
方法二：递归(从前往后改变指针方向)
//方法二:递归法1 先改变指针方向,再继续进行递归 ListNode* reverse(ListNode* pre,ListNode* cur) {//返回值主要是用来递归完成之后返回头结点的,无其他用途 if(cur==NULL) { return pre; } ListNode* temp = cur->next; cur->next = pre;//修改指针方向 return reverse(cur,temp) ; } ListNode* reverseList(ListNode* head) { if(head==NULL||head->next==NULL) { //判断0个和1个节点情况,不用进行反转 return head; } return reverse(NULL,head); }
方法三：递归（从后往前改变指针方向） 目前测试不通过…
//方法三:递归法2 先进行递归,后改变指针方向 ???不知道为啥错了.. ListNode* resNode = new ListNode(-1); ListNode* solve(ListNode* cur) { if(cur==NULL) { //结束条件 return resNode; } ListNode* pre = solve(cur->next); pre->next = cur; return cur; } ListNode* reverseList(ListNode* head) { if(head==NULL||head->next==NULL) { //判断0个和1个节点情况,不用进行反转 return head; } solve(head); ListNode* head = resNode->next; delete resNode; return head; }
24. 两两交换链表中的节点
题目描述
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1：
输入：head = [1,2,3,4] 输出：[2,1,4,3]
示例 2：
输入：head = [] 输出：[]
示例 3：
输入：head = [1] 输出：[1]
思路分析
题目的要求是交换相邻的节点,题目也说了是这两个节点的顺序发生改变,而不是仅仅交换下值.而且如果当前节点只有一个,则肯定不需要交换啦.
接下来我们用图解来表示:
根据图中,我们可以使用三个辅助变量便可完成操作.
参考代码
#include<bits/stdc++.h> using namespace std; //节点定义 struct ListNode{ int val; ListNode* next; ListNode(){} ListNode(int x):val(x),next(nullptr){ } ListNode(int x,ListNode* next):val(x),next(next){ } }; ListNode* swapPairs(ListNode* head) { if(head==NULL||head->next==NULL){//没有结点或者只有一个结点时 return head; } ListNode* dummyHead = new ListNode(-1,head);//创建虚拟头结点 ListNode *cur = dummyHead,*node1,*node2,*node3;//创建当前节点cur以及辅助节点node1、node2、node3 while( cur->next && cur->next->next){ node1 = cur->next; node2 = cur->next->next; node3 = cur->next->next->next; cur->next = node2;//执行第一步:当前0节点指向2号节点 node2->next = node1;//执行第二步:当前2节点指向1号节点 node1->next = node3;//执行第三步:当前1节点指向3号节点. cur = node1;//更新cur } head = dummyHead->next; delete dummyHead; return head; }
