前言
之前小六六一直觉得自己的算法比较菜,算是一个短板吧,以前刷题也还真是三天打鱼,两台晒网,刷几天,然后就慢慢的不坚持了,所以这次,借助平台的活动,打算慢慢的开始开刷,并且自己还会给刷的题总结下,谈谈自己的一些思考,和自己的思路等等,希望对小伙伴能有所帮助吧,也可以借此机会把自己短板补一补,希望自己能坚持下去呀
链表
- 六六力扣刷题链表之移除链表元素
- 六六力扣刷题链表之反转链表
- 六六力扣刷题链表之两两交换链表中的节点
- 六六力扣刷题链表之合并两个有序链表
链表的理论基础
链表的种类主要为:单链表,双链表,循环链表
链表的存储方式:链表的节点在内存中是分散存储的,通过指针连在一起。
链表是如何进行增删改查的。
数组和链表在不同场景下的性能分析。
可以说把链表基础的知识都概括了,但又不像教科书那样的繁琐。
虚拟头结点
链表的一大问题就是操作当前节点必须要找前一个节点才能操作。这就造成了,头结点的尴尬,因为头结点没有前一个节点了。
每次对应头结点的情况都要单独处理,所以使用虚拟头结点的技巧,就可以解决这个问题。
题目
给你单链表的头指针 head 和两个整数 left 和 right ,其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点,返回 反转后的链表 。
输入: head = [1,4,3,2,5,2], x = 3
输出:[1,2,2,4,3,5]
解析
这题其实是下面这题的升级,
这题的代码如下:
public ListNode1 reverseList1(ListNode1 head) {
if (null==head){
return head;
}
ListNode1 pre=null;
ListNode1 curr=head;
while (curr!=null){
ListNode1 next=curr.next;
curr.next=pre;
pre=curr;
curr=next;
}
return pre;
我们来看下新题应该怎么解决
思路
穿针引线
我们以下图中黄色区域的链表反转为例。
package com.six.finger.leetcode.two;
import com.six.finger.leetcode.common.ListNode1;
public class reverseBetween {
public static void main(String[] args) {
ListNode1 head=new ListNode1(1);
ListNode1 listNode1=new ListNode1(2);
head.next=listNode1;
ListNode1 listNode2=new ListNode1(3);
listNode1.next=listNode2;
ListNode1 listNode3=new ListNode1(4);
listNode2.next=listNode3;
ListNode1 listNode11 = reverseBetween(head, 2, 3);
}
public static ListNode1 reverseBetween(ListNode1 head, int left, int right) {
ListNode1 dumy= new ListNode1(0);
dumy.next = head;
ListNode1 pre=dumy;
// 第 1 步:从虚拟头节点走 left - 1 步,来到 left 节点的前一个节点
for (int i = 0; i < left - 1; i++) {
pre = pre.next;
}
// 第 2 步:从 pre 再走 right - left + 1 步,来到 right 节点 此时pre截断了,所以并不会往下走了
ListNode1 rightNode = pre;
for (int i = 0; i < right - left + 1; i++) {
rightNode = rightNode.next;
}
// 第 3 步:切断出一个子链表(截取链表)
ListNode1 leftNode = pre.next;
ListNode1 curr = rightNode.next;
// 注意:切断链接
pre.next = null;
rightNode.next = null;
// 第 4 步:同第 206 题,反转链表的子区间
reverseLinkedList(leftNode);
// 第 5 步:接回到原来的链表中
pre.next = rightNode;
leftNode.next = curr;
return dumy.next;
}
private static void reverseLinkedList(ListNode1 head) {
// 也可以使用递归反转一个链表
ListNode1 pre = null;
ListNode1 cur = head;
while (cur != null) {
ListNode1 next = cur.next;
cur.next = pre;
pre = cur;
cur = next;