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 输出：[]
方法一:使用虚拟头结点
先为原始链表创建一个虚拟头结点,然后在下一个节点存在的情况下,判断下一个节点是否 == val,如果等于则进行删除操作.否则继续遍历.
参考代码1
//使用带虚拟头结点的方法. ListNode* removeElements(ListNode* l, int val) { ListNode* L = new ListNode(-1,l); ListNode* p = L,*q;//注意这里的指针定义. while(p->next!=NULL){//如果当前节点的下一个节点不为空. if(p->next->val==val){ q = p->next; p->next = p->next->next;//指针方向进行变化. delete q;//删除该节点. }else{ p = p->next;//更新p } } p = L->next; delete L; return p; }
方法二:无虚拟头结点
因为头结点前面没有节点,所以如果头结点是我们的删除目标,删除的办法就和删除非头结点的不同,需要特殊处理.
所以基本思路是:
先判断头结点是否 == val,如果等于则直接指针后移,并进行删除该节点.
头结点处理完毕后,继续后序的处理,依次遍历节点,判断当前节点的下一个节点是否 == val,如果等于则进行删除下一个节点.不相等,则指针后移,继续遍历.
参考代码2
ListNode* removeElements(ListNode* l, int val) { //删除头结点. ListNode* temp; while(l!=NULL&&l->val==val){ temp = l; l = l->next; delete temp; } if(l==NULL){//判断头结点是否为null了,如果是,则直接返回NULL. return NULL; } //删除非头结点 (和第一种方法一样) ListNode* cur = l; while(cur->next!=NULL){ if(cur->next->val==val){ temp = cur->next; cur->next = cur->next->next; delete temp; }else{ cur = cur->next; } } return l; }
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继续遍历下一个节点,直至链表遍历完毕.
参考代码1
//双指针法 ListNode* reverseList(ListNode* head) { ListNode* cur = head; ListNode* pre = NULL; ListNode* temp;//用于保存当前节点的下一个节点. while(cur){ temp = cur->next; cur->next = pre;//改变当前节点的指针方向. pre = cur;//pre指针后移 cur = temp;//当前节点后移. } return pre; }
方法二:递归1(从前往后改变指针方向)
思路和方法一基本一致,递归实际上就是自己调用自己,每次的操作一致.
- 每次我们需要改变指针指向,需要操作两个节点,当前节点cur和上一个节点pre,所以这就是递归函数的参数.
- 递归的结束条件就是当前节点为NULL,则不再需要改变方向了.递归结束.
参考代码2
//递归本质上就是在做相同的操作,自己不断的调用自己. 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) { return reverse(NULL,head); }
方法三:递归2(从后往前改变指针方向)
后期进行完善…
24. 两两交换链表中的节点
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1：
输入：head = [1,2,3,4] 输出：[2,1,4,3]
示例 2：
输入：head = [] 输出：[]
示例 3：
输入：head = [1] 输出：[1]
思路分析
题目的要求是交换相邻的节点,题目也说了是这两个节点的顺序发生改变,而不是仅仅交换下值.而且如果当前节点只有一个,则肯定不需要交换啦.
两个数进行交换我们需要一个中间值.而两个节点 1, 2 进行交换涉及到当前节点 0 的指向,A,B这两个节点的指针指向.
接下来我们用图解来表示:
根据图中,我们可以使用三个辅助变量便可完成操作.
参考代码
ListNode* swapPairs(ListNode* l) { ListNode* head = new ListNode(-1,l); ListNode* cur = head; ListNode* temp1,temp2,temp3;//分别存放,当前节点后面的三个节点,便于操作. while(cur->next!=NULL&&cur->next->next!=NULL){ temp1 = cur->next; temp2 = cur->next->next; temp3 = cur->next->next->next; cur->next = temp2;//执行第一步:当前0节点指向2号节点 temp2->next = temp1;//执行第二步:当前2节点指向1号节点 temp1->next = temp3;//执行第三步:当前1节点指向3号节点. cur = cur->next->next;//cur后移两位. } return head->next; }
19. 删除链表的倒数第 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]
思路分析
快慢指针
先搞一个虚拟头结点,方便我们接下来的操作.
第一步slow和fast都指向虚拟头结点.
第二步fast向前移动n+1个节点
slow和fast同时向前移动,直至fast为空,则slow对应的便是目标节点的前一个节点.
为啥fast要先移动n+1个节点呢?why?
因为这样的话,之后当fast和slow同时移动,当fast为null时,slow对应的刚好是target前一个节点. 而如果是n,则slow对应的是目标节点.
参考代码
ListNode* removeNthFromEnd(ListNode* l, int n) { ListNode* head = new ListNode(-1,l); ListNode* fast = head,*slow= head; while(n--&&fast){ fast = fast->next; } fast = fast->next;//fast再向前走一步,因为需要让slow指向删除节点的上一个节点 while(fast){ fast=fast->next; slow = slow->next; } slow->next = slow->next->next; return head->next; }
