1.访问链表中的某一特殊位置的节点
876.访问链表的中间节点:快指针是慢指针移动速度的二倍,快指针到结尾,慢指针到中间。
19.删除链表的倒数第N个节点:可理解为访问链表倒数第N+1个节点。快指针先走N+1步,然后快慢指针同速走,快指针到结尾空节点,慢指针到倒数第N+1节点。
2.删除链表中满足某一特殊条件的节点
237.删除链表中的节点:直接给出了要删除的节点,先把这个节点的值换成它的下一个节点的值,然后利用这个节点删除它的下一个节点。
203.移除链表val=6的元素:因为head有可能被移除,所以设置dummyNode.站在前一个节点判断其后面节点是否需要被删除。
83.删除排序链表中的重复节点(保留一个):快慢指针,快指针遇到和慢指针相同的val则快指针后移,慢指针不动;快指针遇到和慢指针不同的val则慢指针的下一个节点指向快指针,慢指针直接跳到快指针,快指针跳到下一个节点。当快指针指到为节点,慢指针的下一个节点指向快指针。
82。删除排序链表中的重复节点(重复的一个不留):因为head有可能被删除,所以设置dummyNode.设置前驱节点保留被删除节点的前一个节点。剩下考虑如何确定被删除的节点,设置一个快指针,根据当前节点和下一个节点的val是否重复,决定快指针和前驱指针的移动方法。
3.两链表合并问题
2.两数相加:两链表以相加的形式进行合并。设置结果链表的preHead,因为需要创建head。循环时等两个列表都走到尾为结束条件,其中必然有一个先走到结尾,则先走到结尾的不继续next,并且把它缺少的位数看做0占位。
445.两数相加II:和上一题相比主要差别在于,上一题数字在链表中低位在前,本题数字在链表中是高位在前。上一题可以按照访问的顺序做加法,本题不行。如果先走到链表结尾就没办法往回加了,同时题目要求不能改变(翻转)链表。所以借助stack,把两个链表反向存储,然后按照上一题的方法做就行了。
21.合并两个有序链表:设置preHead节点,同时对两个链表进行遍历,每次取较小的节点作为待合并节点,以最短链表到头为循环结束条件。剩余的部分直接连接到后面。
23.合并K个排序链表:在合并两个的基础上,组对合并(可相邻组对,也可采用头尾组对)
4.旋转列表相关(完全或者部分)
206.反转链表:核心操作是当前节点指针指向前一个节点,辅助操作是保存当前节点的下一个节点,因为完成核心操作后,下一个节点就丢失了。
92.反转链表II:核心操作和上一题一样,辅助操作是找到反转区间的前一个节点,以便最后接上。
234.回文链表:找链表中点+链表反转
61.旋转链表:核心操作是找到链表的断开点,重新组织两段链表。辅助操作是招到第k%len个节点。
24.两两交换链表节点:链表反转的基本操作。
25.K个一组进行翻转:反转列表II的迭代版,注意保存好反转区间的前驱节点。