单链表的基本实现及解决leetcode 反转链表

文章目录

• 一、单链表的基本实现源码
• 二、反转链表
• • 1、题目描述
  • 2、思路
  • 3、源码

一、单链表的基本实现源码

public class LinkedList<T> {
/**
* 链表大小
*/
private int size = 0;

/**
* 节点属性
*/
private class Node {
private T value;
private Node next;
public Node(){
}
public Node(T value) {
this.value = value;
}

public T getValue() {
return this.value;
}
public Node getNext() {
return this.next;
}
}

/**
* 头节点
*/
Node head = new Node();

/**
* 插入节点
* @param value
* @param index
*/
public void add(T value, int index) {
if (index < 0 || index > size){
throw new IndexOutOfBoundsException();
}
Node prev = head;
for (int i = 0; i < index; i++) {
prev = prev.next;
}
Node newNode = new Node(value);
newNode.next = prev.next;
prev.next = newNode;
size++;
}

/**
* 查询节点
* @param index
*/
public T get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
Node prev = head;
for (int i = 0; i < index; i++) {
prev = prev.next;
}
return prev.next.getValue();
}

/**
* 删除节点
* @param index
*/
public void remove(int index) {
if(index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
Node prev = head;
for (int i = 0; i < index; i++) {
prev = prev.next;
}
prev.next = prev.next.next;
size—;
}

/**
* 重写toString方法
*/
@Override
public String toString() {
if(head.next == null) {
return "[]";
}
StringBuilder builder = new StringBuilder();
Node current = head.next;
builder.append("[");
while(current != null) {
builder.append(current.getValue()).append(", ");
current = current.next;
}
builder.append("]");
return builder.toString();
}

二、反转链表

1、题目描述

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

2、思路

  使用双指针法解决反转问题；有两个指针 pre 和 cur pre 首先指向 null，cur 则指向 head 头节点

3、源码

/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null) {
return head;
}
ListNode pre = null;
ListNode cur = head;
while(cur != null) {
ListNode tmp = cur.next;
cur.next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
}