链表专题-01

链表问题

链表回顾

数据结构分类

线性

非线性

节点结构

节点{

 	 data //数据

	 next //下一个节点的位置
  }

/**
 * 链表的节点
 * @param <E>
 */
public class ListNode<E> {
    public E element;
    public ListNode<E> next;


    public ListNode() {
    }

    public ListNode(E element) {
        this.element = element;
    }

    public ListNode(E element, ListNode<E> next) {
        this.element = element;
        this.next = next;
    }

    @Override
    public String toString() {
        return "ListNode{" +
                "element=" + element +
                ", next=" + next +
                '}';
    }
}

链表结构

经典问题

反转链表

问题

[力扣206] 206. 反转链表 - 力扣（LeetCode）

问题描述

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

解决方案

迭代法

虚拟头结点。

第二次循环

循环之后: 虚拟头结点连接末尾元素

递归法

递归查找到尾节点的前一个节点（curr.next)

• 递归跳出条件 (curr== null || curr.next == null)

1. 尾节点(curr.next) 连接当前节点(curr): curr.next.next = curr;

2. 断开curr节点与前一个节点: curr.next = null;

3. 最后一个节点反转完成，倒数第二个节点(4)断开与倒数第三个节点（3）连接。

递归其它节点

反转链表II

问题

[力扣92] 92. 反转链表 II - 力扣（LeetCode）

问题描述

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

示例 1：

输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]

示例 2：

输入：head = [5], left = 1, right = 1
输出：[5]

解决方案

定义虚拟头节点dummy, 要操作节点的前一个节点pre（默认为null）, 寻找的反转节点的前一个节点first（默认指向dummy节点）

index记录查找到left的步数，tips：left位置从1开始计算，所以我们要寻找的位置应该left-1;

移动first索引查找要操作的元素的前一个节点(节点1)。

记录当前要操作的节点curr，使用curr对要求的节点进行反转操作。

1. Node next = curr.next;
2. curr.next = pre;
3. pre = curr;
4. curr = next;

重复执行操作2,3,4节点，出循环后

1. first.next.next = curr; //即节点2 连接节点5
2. first.next = pre； //即节点1连接要操作的最后一个节点

重复执行操作2,3,4节点，出循环后

1. first.next.next = curr; //即节点2 连接节点5
2. first.next = pre； //即节点1连接要操作的最后一个节点

public ListNode reverseList(ListNode head) {
        if(head==null || head.next==null) return head;

        ListNode last=reverseList(head.next);
        head.next.next=head;
        head.next=null;
        return last;
    }