- 系列文章目录
- 链表基础
- 707. 设计链表
- 链表：双指针思路
- 203. 移除链表元素
- 206. 反转链表
- 24. 两两交换链表中的节点
- 链表：快慢指针思路
- 19. 删除链表的倒数第 N 个结点
- 160. 相交链表
- 141. 环形链表
- 142. 环形链表 II
- 总结
刷题笔记（一）–数组类型：二分法
刷题笔记（二）–数组类型：双指针法
刷题笔记（三）–数组类型：滑动窗口
刷题笔记（四）–数组类型：模拟
关于链表的构造，在我之前的博客中其实都是写过的，这里更多的就是复习。
LinkedList与链表
其实不论怎么构造，主要就是要理解链表的特点。所以还是用下面的题来进行讲解
707. 设计链表
题目截图：
注意我这里的思路是有点不一样的，主要体现在我初始化的时候没有说给头结点和尾结点构造一个虚拟节点，由此后续很多细节性的处理就很不同。
public class MyLinkedList {
static class ListNode{
int value;//定义每个节点的值
ListNode prev;//定义前节点
ListNode next;//定义后节点
public ListNode(int e){
value = e;
}
}
int size;//定义链表的节点长
ListNode head;//定义一个虚拟头节点
ListNode tail;//定义一个虚拟尾结点
public MyLinkedList(){
size = 0;
}
public int get(int index) {
//先判断index是否合理
if(index < 0 || index > size - 1){
return -1;
}
int count = 0;
ListNode tmp = head;
//合理的话就再往下走
while(count < index){
tmp = tmp.next;
count++;
}
return tmp.value;
}
public void addAtHead(int val) {
ListNode node = new ListNode(val);
//这里先判断一下元素是否为空，如果为空就是首尾元素都指向一个节点
if(size == 0){
tail = node;
}else{
//如果不为空那就把新的节点设置为头结点
node.next = head;
head.prev = node;
}
head = node;
size++;
}
//这里的思路和头插法一致
public void addAtTail(int val) {
ListNode node = new ListNode(val);
if(size == 0){
head = node;
}else{
tail.next = node;
node.prev = tail;
}
tail = node;
size++;
}
public void addAtIndex(int index, int val) {
if(index <= 0){
addAtHead(val);
}else if(index == size){
addAtTail(val);
}else if(index > size){
return;
}else{
//这里的话就不构造虚拟节点了，就直接从头结点开始遍历，然后直接插到对应节点的头结点就好
int count = 0;
ListNode tmp = head;
ListNode node = new ListNode(val);
while(count < index){
tmp = tmp.next;
count++;
}
//插入节点的话就要先处理待插入的节点，不能动原节点
node.next = tmp;
node.prev = tmp.prev;
//这里的话就开始对原节点开始处理
tmp.prev.next = node;
tmp.prev = node;
size++;
}
}
public void deleteAtIndex(int index) {
if(index >= size || index < 0){
return;
}
if(index == 0){
head = head.next;
}else if(index == size - 1){
tail = tail.prev;
}else{
ListNode tmp = head;
int count = 0;
while(count < index){
count++;
tmp = tmp.next;
}
tmp.prev.next = tmp.next;
tmp.next.prev = tmp.prev;
}
size--;
}
}
203. 移除链表元素
关于这个题的话，之前也写过相关的博客。关于题目本身需要注意一下的情况
<1>输入[7,7,7,7,7]数组，删除为7的元素
<2>输入[]数组
<3>输入[7,1,2,3,4,5]数组，删除为7的元素
关于题目自身需要注意的就是以上的测试用例。不论那种解法都要考虑以上的情况的处理。
不
定
义
虚
拟
节
点
\color{red}{不定义虚拟节点}
不定义虚拟节点
/*关于这种解法，就是最最麻烦的一种解法，因为要分情况进行判断，每种情况有不同的处理*/
class Solution {
public ListNode removeElements(ListNode head, int val) {
//首先排除第一个节点value是val的情况
while(head != null && head.val == val){
head = head.next;
}
//然后准备进行删除
ListNode key = head;
if(key != null){//要先排除空数组的情况
while(key.next != null){//然后进行删除 *** 作
//删除分情况讨论
if(key.next.val == val){
key.next = key.next.next;
}else{
key = key.next;
}
}
}
return head;
}
}
定 义 虚 拟 节 点 \color{red}{定义虚拟节点} 定义虚拟节点
/*这种方法呢就会方便很多，因为我不需要进行那么多的判断了，我一个虚拟节点就可以搞定所有的情况*/
public class 移除链表元素 {
public ListNode removeElements(ListNode head, int val) {
ListNode node = new ListNode(0);
ListNode tmp = node;
node.next = head;
while (tmp.next != null){
if(tmp.next.val == val){
tmp.next = tmp.next.next;
}else{
tmp = tmp.next;
}
}
return node.next;
}
}
递
归
\color{red}{递归}
递归
这种的话就比较考验基本功了，当然笔者当时是没有想到的，是之后才看到的。
public class 移除链表元素_递归版本 {
public ListNode removeElements(ListNode head, int val) {
if(head == null){
return head;
}
head.next = removeElements(head.next,val);
return head.val == val ? head.next:head;
}
}
206. 反转链表
这里还是有两种方法的，迭代和递归都是可以的。
迭 代 \color{red}{迭代} 迭代
public class 反转链表 {
public ListNode reverseList(ListNode head) {
ListNode node = null;//定义一个虚拟节点
ListNode slow = head;
ListNode fast = null;
while(slow != null){
fast = slow.next;
slow.next = node;//进行反转
//反转之后的处理
node = slow;
slow = fast;
}
return node;
}
}
递 归 \color{red}{递归} 递归
public class 反转链表_递归版本 {
public ListNode reverseList(ListNode head) {
return reverseList(null,head);
}
//递归版本其实重点就是弄清楚临界条件和每一次的递归都做了什么
public ListNode reverseList(ListNode pre,ListNode cur) {
if(cur == null){
//每一次的反转其实就是当前节点和当前节点的前一个节点进行反转
return pre;
}
//定义当前节点的下一个节点用来充当下一次方法调用的cur，当前cur就是下一次的pre
ListNode fac = cur.next;
cur.next = pre;
return reverseList(cur,fac);
}
}
24. 两两交换链表中的节点
public static ListNode swapPairs(ListNode head) {
ListNode slow = head;
/*
while条件判断含义：
保证可以有元素进行交换
*/
while(slow != null && slow.next != null){
ListNode fast = slow.next;
int tmp = slow.val;
slow.val = fast.val;
fast.val = tmp;
//这里就是要判断了，当前节点交换完之后下下个节点必须要有节点，不然就不用交换
if(slow.next.next != null){
slow = slow.next.next;
}else{
break;
}
}
return head;
}
19. 删除链表的倒数第 N 个结点
这个题目细节其实还是很多的，思路就很好想，但是实际 *** 作起来细节还真不那么容易把控。
public class 删除倒数N节点 {
public ListNode removeNthFromEnd(ListNode head, int n) {
//第一个细节就是要用虚拟节点来进行 *** 作，这样可以忽视许多特殊的输入
ListNode node = new ListNode(0,head);
ListNode fast = head;
while(n > 0){
fast = fast.next;
n--;
}
ListNode slow = node;
//这里当fast走完之后，为null的时候,slow的下一个节点就是要删除的节点。
while(fast != null){
slow = slow.next;
fast = fast.next;
}
//然后进行删除，这里slow不为空的原因是因为,fast走过的路程一定是不为null的
slow.next = slow.next.next;
return node.next;
}
}
160. 相交链表
关于这道题其实就是关键点想通就好，怎样知道有没有相交的节点呢？就是让它们走一样的路程，最后看会不会相遇，也就是：
a1一直走，走到c3之后，跳到b1继续往下走
b1一直走，走到c3之后，跳到a1继续往下走
如果说有相交节点，那么一轮走下来之后肯定是会相遇的
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null || headB == null){
return null;
}
ListNode listA = headA;
ListNode listB = headB;
while(listA != listB){
listA = listA == null ? headB : listA.next;
listB = listB == null ? headA : listB.next;
}
return listA;
}
}
141. 环形链表
这个就是一个很典型的快慢指针的题，但是要注意，一个走奇数步，一个走偶数不，不能两个一样的奇偶数。
public class 环形链表 {
public boolean hasCycle(ListNode head) {
//如果是空节点或者说是只有一个节点就不需要判断了
if(head == null || head.next == null){
return false;
}
ListNode slow = head;
ListNode fast = head;
//这里注意了嗷，一定要是fast != null 并且 fast.next != null，如果为空，那就直接到头了，就不是个环
while (fast != null && fast.next != null){
//慢指针一次走一步，快指针一次走两步
slow = slow.next;
fast = fast.next.next;
if(slow == fast){
return true;
}
}
return false;
}
}
142. 环形链表 II
做这个题是有一个隐藏的知识点的，怎么说呢？就是快慢指针一前一后的出发，在环形链的某一点它们会相遇。相遇的这个点，距离环形链的入口的距离（这个距离指的是前进方向和入口的距离）等于头结点距离环形链入口的距离。所以知道了这一点之后，其实就很简单了，无非就是在快慢指针相遇的时候加一个判断语句。
public class Solution {
public ListNode detectCycle(ListNode head) {
//首先判断是否有环
if(head == null || head.next == null){
return null;
}
ListNode fast = head;
ListNode slow = head;
ListNode key1 = head;
ListNode key2 = null;
while (fast !=null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
//如果能碰到，就证明有环，那就进入下个判断
if(slow == fast){
key2 = slow;
//这个时候如果key1 == key2，那就是环形链表的入口了
while(key1 != key2){
key1 = key1.next;
key2 = key2.next;
}
return key1;
}
}
return null;
}
}
关于这一个篇章，其实回想一下，没有什么所谓的做题模板，就是考验对于细节的把控，还有就是要善于利用虚拟节点来解题。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）