前言
之前小六六一直觉得自己的算法比较菜，算是一个短板吧，以前刷题也还真是三天打鱼，两台晒网，刷几天，然后就慢慢的不坚持了，所以这次，借助平台的活动，打算慢慢的开始开刷，并且自己还会给刷的题总结下，谈谈自己的一些思考，和自己的思路等等，希望对小伙伴能有所帮助吧，也可以借此机会把自己短板补一补，希望自己能坚持下去呀
链表
链表的理论基础
链表的种类主要为：单链表，双链表，循环链表 链表的存储方式：链表的节点在内存中是分散存储的，通过指针连在一起。 链表是如何进行增删改查的。 数组和链表在不同场景下的性能分析。 可以说把链表基础的知识都概括了，但又不像教科书那样的繁琐。
虚拟头结点
链表的一大问题就是操作当前节点必须要找前一个节点才能操作。这就造成了，头结点的尴尬，因为头结点没有前一个节点了。
每次对应头结点的情况都要单独处理，所以使用虚拟头结点的技巧，就可以解决这个问题。
题目
给你单链表的头指针 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; }
我们来看下新题应该怎么解决
思路
穿针引线 我们以下图中黄色区域的链表反转为例。
使用「206. 反转链表」的解法，反转 left 到 right 部分以后，再拼接起来。我们还需要记录 left 的前一个节点，和 right 的后一个节点。如图所示：
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; } } }
结束
好了，这题还是有点小难的，大家加油，我是小六六，三天打鱼，两天晒网！
