链表
链表 : 跳转结构
一 . 单链表
单链表: 值,一条next指针
public static class Node {public int value;public Node next;public Node(int data) {value = data;}}
二. 双链表
双链表: 值,一条last指针,一条next指针
public static class DoubleNode {public int value;public DoubleNode last;public DoubleNode next;public DoubleNode(int data) {value = data;}}
三. 反转链表
(一)单链表
思路
- 需要一个 后指针
cur指向head需要一个前指针pre指向nulltemp记录环境(初始为null) - 如果
head位置有值 - 将
head.next位置保存到temp里面 - 将
head.next指向pre pre指向headhead指向temp- 循环2~6
链表结构代码
public static class Node {public int value;public Node next;public Node(int data) {value = data;}}
反转实现代码
public static Node reverseLinkedList(Node head) {Node pre = null;Node next = null;while (head != null) {next = head.next;head.next = pre;pre = head;head = next;}return pre;}
(二)双链表
思路
- 需要一个 后指针
cur指向null 需要一个前指针pre指向nulltemp记录环境(初始为null) - 如果
head位置有值 head的next指针保存到temp(当前为null)head的last指针指向nextpre指向headhead指向temp- 循环2~6
链表结构代码
public static class DoubleNode {public int value;public DoubleNode last;public DoubleNode next;public DoubleNode(int data) {value = data;}}
反转实现代码
public static Node reverseLinkedList(Node head) {Node pre = null;Node next = null;while (head != null) {next = head.next;head.next = pre;pre = head;head = next;}return pre;}
剑指 Offer 24. 反转链表
// head// a -> b -> c -> null// c -> b -> a -> nullpublic static Node reverseLinkedList(Node head) {Node pre = null;Node next = null;while (head != null) {next = head.next; //用next记录下一个节点head.next = pre;pre = head;head = next;}return pre;}
四. 单链表简单操作
public class Mylist {public Node head; //定义一个头结点public Node current; //当前结点//添加元素public void add(int data){//判断链表是否为空if(head==null) //如果头结点为空,说明这个链表还没有被创建{head = new Node(data);current = head;}else{//创建新的结点Node node = new Node(data);//放在当前结点的后面current.next=node;//把链表的当前索引向后移动一位current=current.next;}}//获取单链表的长度public int getLength(){//头结点为空则返回0if(head==null)return 0;else{int length=0;Node current = head;while(current!=null){current=current.next;length++;}return length;}}//打印链表public void printList(){Node tmp = head;while(tmp!=null){System.out.println(tmp.data+" ");tmp=tmp.next;}}//删除第index个结点public boolean deleteNode(int index){if(index<1||index>this.getLength())return false;if(index==1){head=head.next;return true;}int i =1;Node proNode = head;Node curNode = proNode.next;while(curNode!=null){if(i==index){proNode.next=curNode.next;return true;}proNode = curNode;curNode = curNode.next;i++;}return false;}//链表反转 遍历实现public static Node Reverse(Node head){if(head==null||head.next==null)return head;Node pre=head; //上一结点Node cur=head.next; //当前结点Node tmp ;//临时结点,用于保存当前指针域while(cur!=null){tmp=cur.next;cur.next=pre; //反转指向//指针向下移动pre=cur;cur=tmp;}head.next=null ;//将头结点设空return pre;}//判断单链表是否有环,我们用两个指针去遍历：//first指针每次走一步，second指针每次走两步，如果first指针和second指针相遇，说明有环。public boolean hasCycle(Node head) {if (head == null) {return false;}Node first = head;Node second = head;while (second != null) {first = first.next; //first指针走一步second = second.next.next; //second指针走两步if (first == second) { //一旦两个指针相遇，说明链表是有环的return true;}}return false;}}
五. 双向链表简单操作
public class DoubleLinkList {//头private Node first;//尾private Node last;public DoubleLinkList(){first = null;last = null;}/*** 插入数据* @param value*/public void insertFirst(long value){Node newNode = new Node(value);if (first == null) {last = newNode;}else {first.previous = newNode;//把first节点往下移动newNode.next = first;}//把插入的节点作为新的节点first = newNode;}/*** 插入数据* @param value*/public void insertLast(long value){Node newNode = new Node(value);if (first == null) {first = newNode;}else {last.next = newNode;//first.previous = newNode;newNode.previous = last;}//把最后个节点设置为最新的节点last = newNode;}public boolean isEmpty(){return first == null;}/*** 删除头节点时要去除两个指针,一个指向下个的next ,一个是next的previous指向前面的** @param value* @return*/public Node deleteFirst(){if (first == null) {throw new RuntimeException("链表数据不存在");}Node temp = first;if (first.next == null) {last = null;}else {first.next.previous = null;}first = temp.next;return temp;}/*** 删除头节点时要去除两个指针,一个指向下个的next ,一个是next的previous指向前面的** @param value* @return*/public Node deleteLast(){if (first == null) {throw new RuntimeException("链表数据不存在");}Node temp = last;if (first.next == null) {last = null;//把第一个删除first = null;}else {last.previous.next = null;}last = temp.previous;return temp;}/*** 删除* @param key* @return*/public Node deleteByKey(long key){Node current = first;while(current.data != key){if (current.next == null) {System.out.println("没找到节点");return null;}current = current.next;}if (current == first) {//return deleteFirst();//指向下个就表示删除第一个first = first.next;}else {current.previous.next = current.next;}return current;}/*** 显示所有的数据*/public void display(){if (first == null) {//throw new RuntimeException("链表数据不存在");return;}Node current = first;while(current != null){current.display();current = current.next;}System.out.println("---------------");}/*** 查找节点1* @param value* @return*/public Node findByValue(long value){Node current = first;while(current != null){if (current.data != value) {current = current.next;}else {break;}}if (current == null) {System.out.println("没找到");return null;}return current;}/*** 查找节点2** @param key* @return*/public Node findByKey(long key) {Node current = first;while (current.data != key) {if (current.next == null) {System.out.println("没找到");return null;}current = current.next;}return current;}/*** 根据索引查找对应的值* @param position* @return*/public Node findByPosition(int position){Node current = first;//为什么是position - 1，因为要使用遍历，让current指向下一个， 所以position - 1的下个node就是要找的值for (int i = 0; i < position - 1 ; i++) {current = current.next;}return current;}}
剑指 Offer 18. 删除链表的节点
public class DeleteGivenValue {
public static class ListNode {
public int val;
public ListNode next;
public ListNode(int data) {
this.val = data;
}
}
// head = removeValue(head, 2);
public ListNode deleteNode(ListNode head, int num) {
// head来到第一个不需要删的位置
while (head != null) {
if (head.val != num) {
break;
}
head = head.next;
}
// 1 ) head == null
// 2 ) head != null
ListNode pre = head;
ListNode cur = head;
while (cur != null) {
if (cur.val == num) {
pre.next = cur.next;
} else {
pre = cur;
}
cur = cur.next;
}
return head;
}
}
六. 静态链表
package com.yds.list;
/**
* 因为静态链表实质上是一维数组的存储方式，所以它在物理位置上的存储
* 是顺序的，但它是用游标来指向下一个数据的，所以根据它的下标来获取数据
* 和按照游标的指向来获取数据是不同的，这里设置该链表的头结点为空
* @author Administrator
*
*/
public class StaticLinkList {
private Element[] linkList = null;
// private Element[] linkList1 = null;
private int DEFAULT_SIZE = 4;//默认存储大小
private int currentFree = 0;//指向当前空闲位置
private int size = 1;
class Element{
int data;
int cur;
}
/**
* 静态链表的长度
* @return
*/
public int length(){
return size-1;
}
/**
* 静态链表的初始化
*/
public StaticLinkList(){
linkList = new Element[DEFAULT_SIZE];
for (int i = 0; i < linkList.length; i++) {
linkList[i] = new Element();
linkList[i].data = -1;
linkList[i].cur = i+1;
}
//当前空闲节点从1开始，因为第0个节点设置成了头结点，设置为空，不
//存储数据
currentFree = 1;
}
/**
* 给链表添加数据，每当链表满了就给链表添加额外的空间
* @param data
*/
public void add(int data){
if(size<linkList.length){
linkList[currentFree].data = data;
currentFree = linkList[currentFree].cur;
size++;
}else{//链表已满，给链表添加空间
addLinkSpace();
linkList[currentFree].data = data;
currentFree = linkList[currentFree].cur;
size++;
}
}
/**
* 得到索引指定的数据
* @param index
* @return
*/
public int get(int index){
if(index>size-1&&index<0)
throw new IndexOutOfBoundsException("数组越界，索引不合法");
else{
//这里index+1也是因为多了一个空的头节点
return linkList[index+1].data;
}
}
/**
* 删除指定位置的节点
* @param index
*/
public void delete(int index){
index = index+1;
if(index<1||index>=size){
System.out.println("超出链表长度");
}else if(index == size-1){
size--;
linkList = (Element[]) getTrueIndex(linkList,size);
}else{
int i = 0;
while(index!=linkList[i].cur){
i++;
}
int j = 0;
while(currentFree!=linkList[j].cur){
j++;
}
linkList[i].cur = linkList[index].cur;
linkList[j].cur = index;
linkList[index].cur = currentFree;
currentFree = index;
size--;
linkList = (Element[]) getTrueIndex(linkList,size);
}
}
/**
* 增加链表空间
*/
public void addLinkSpace(){
DEFAULT_SIZE+=8;
Element[] link = linkList;
linkList = new Element[DEFAULT_SIZE];
System.arraycopy(link, 0, linkList, 0, link.length);
for (int i = link.length; i < DEFAULT_SIZE; i++) {
linkList[i] = new Element();
linkList[i].data = -1;
linkList[i].cur = i+1;
}
currentFree = link.length;
}
/**
* 根据指定的位置插入数据
* @param index
* @param data
*/
public void insert(int index,int data){
//这里加1的原因是因为链表的第0位为空节点，这里设置的头节点为空
index = index + 1;
if(size<linkList.length){
if(index>size&&index<0)
System.out.println("数组越界，超出数组长度");
else if(index == size){
linkList[currentFree].data = data;
currentFree = linkList[currentFree].cur;
size++;
}else{
/******未按逻辑顺序排序而插入数据的写法，因为未排序，则当前索引的上个节点的索引不一定是当前索引减1****/
int i = 0;
while(index!=linkList[i].cur){
i++;
}
int j = 0;
while(currentFree!=linkList[j].cur){
j++;
}
linkList[i].cur = currentFree;
linkList[j].cur = linkList[currentFree].cur;
linkList[currentFree].data = data;
linkList[currentFree].cur = index;
currentFree = linkList[j].cur;
size++;
//每次插入后将链表按逻辑顺序重新排序，是为了方便输出查看。
linkList = (Element[]) getTrueIndex(linkList,size);
}
}else{
addLinkSpace();
insert(index, data);
}
}
/**
* 按照逻辑顺序重新排列
* @param link
* @return
*/
public Object getTrueIndex(Element[] link,int size){
Element[] linkList1 = new Element[linkList.length];
int k =0;
for (int i = 0; i < linkList.length; i++) {
linkList1[i] = new Element();
linkList1[i].data = link[k].data;
k = link[k].cur;
linkList1[i].cur = i+1;
}
//插入时，currentFree肯定是最后一个了，但删除后，currentFree就不一定是最后一位了
currentFree = size;
return linkList1;
}
}
七. 单链表实现栈和队列
队列 : 先进先出
栈 : 先进后出 , 后进先出
时间复杂度都是 O(1)
队列结构
public static class Node<V> {
public V value;
public Node<V> next;
public Node(V v) {
value = v;
next = null;
}
}
public static class MyQueue<V> {
private Node<V> head;
private Node<V> tail;
private int size;
public MyQueue() {
head = null;
tail = null;
size = 0;
}
public boolean isEmpty() {
return size == 0;
}
public int size() {
return size;
}
public void offer(V value) {
Node<V> cur = new Node<V>(value);
if (tail == null) {
head = cur;
tail = cur;
} else {
tail.next = cur;
tail = cur;
}
size++;
}
// C/C++的同学需要做节点析构的工作
public V poll() {
V ans = null;
if (head != null) {
ans = head.value;
head = head.next;
size--;
}
if (head == null) {
tail = null;
}
return ans;
}
// C/C++的同学需要做节点析构的工作
public V peek() {
V ans = null;
if (head != null) {
ans = head.value;
}
return ans;
}
}
栈结构
public static class MyStack<V> {
private Node<V> head;
private int size;
public MyStack() {
head = null;
size = 0;
}
public boolean isEmpty() {
return size == 0;
}
public int size() {
return size;
}
public void push(V value) {
Node<V> cur = new Node<>(value);
if (head == null) {
head = cur;
} else {
cur.next = head;
head = cur;
}
size++;
}
public V pop() {
V ans = null;
if (head != null) {
ans = head.value;
head = head.next;
size--;
}
return ans;
}
public V peek() {
return head != null ? head.value : null;
}
}
双端队列
public class Code03_DoubleLinkedListToDeque {
public static class Node<V> {
public V value;
public Node<V> last;
public Node<V> next;
public Node(V v) {
value = v;
last = null;
next = null;
}
}
public static class MyDeque<V> {
private Node<V> head;
private Node<V> tail;
private int size;
public MyDeque() {
head = null;
tail = null;
size = 0;
}
public boolean isEmpty() {
return size == 0;
}
public int size() {
return size;
}
public void pushHead(V value) {
Node<V> cur = new Node<>(value);
if (head == null) {
head = cur;
tail = cur;
} else {
cur.next = head;
head.last = cur;
head = cur;
}
size++;
}
public void pushTail(V value) {
Node<V> cur = new Node<>(value);
if (head == null) {
head = cur;
tail = cur;
} else {
tail.next = cur;
cur.last = tail;
tail = cur;
}
size++;
}
public V pollHead() {
V ans = null;
if (head == null) {
return ans;
}
size--;
ans = head.value;
if (head == tail) {
head = null;
tail = null;
} else {
head = head.next;
head.last = null;
}
return ans;
}
public V pollTail() {
V ans = null;
if (head == null) {
return ans;
}
size--;
ans = tail.value;
if (head == tail) {
head = null;
tail = null;
} else {
tail = tail.last;
tail.next = null;
}
return ans;
}
public V peekHead() {
V ans = null;
if (head != null) {
ans = head.value;
}
return ans;
}
public V peekTail() {
V ans = null;
if (tail != null) {
ans = tail.value;
}
return ans;
}
}
八. 题
1. 合并两个有序链表
方法一:迭代
public class Code06_MergeTwoSortedLinkedList {
// 不要提交这个类
public static class ListNode {
public int val;
public ListNode next;
}
class Solution {
public static ListNode mergeTwoLists(ListNode head1, ListNode head2) {
//如果其中有一个链表为空,直接返回另一个
if (head1 == null || head2 == null) {
return head1 == null ? head2 : head1;
}
//头指针指向两个链表头节点值较小的那个,抓到链表头结点用于返回结果
ListNode head = head1.val <= head2.val ? head1 : head2;
//用cur1记录头节点的下一个节点
ListNode cur1 = head.next;
//cur2指向另一个链表的头结点
ListNode cur2 = head == head1 ? head2 : head1;
//pre动态指针指向头结点
ListNode pre = head;
//当cur1和cur2都不为空的时候进入循环
while (cur1 != null && cur2 != null) {
//如果cur1的值小于等于cur2的值
if (cur1.val <= cur2.val) {
//将头结点的next指针指向cur1
pre.next = cur1;
//cur1向后移动
cur1 = cur1.next;
//如果cur1的值大于cur2的值
} else {
//将头节点的next指针指向cur2
pre.next = cur2;
//cur2向后移动
cur2 = cur2.next;
}
//pre指针向后移动
pre = pre.next;
}
//如果头结点的下一个节点为空,意味着其中合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
pre.next = cur1 != null ? cur1 : cur2;
//返回头指针
return head;
}
}
方法二:递归
class Solution {
public static ListNode mergeTwoLists(ListNode head1, ListNode head2) {
//如果head1为空,直接返回head2
if(head1 == null){
return head2;
}
//如果head2为空,直接返回head1
if(head2 == null){
return head1;
}
//如果head1的值小于head2的值
if(head1.val < head2.val){
//将head1的next指针指向(head1的下一个节点 和 head2)的合并
head1.next = mergeTwoLists(head1.next,head2);
//返回head1
return head1;
}
//相反
else{
head2.next = mergeTwoLists(head1,head2.next);
return head2;
}
}
}
2. 两数相加
public class Code05_AddTwoNumbers {
// 不要提交这个类
public static class ListNode {
public int val;
public ListNode next;
public ListNode(int val) {
this.val = val;
}
public ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
public static ListNode addTwoNumbers(ListNode head1, ListNode head2) {
int len1 = listLength(head1);
int len2 = listLength(head2);
ListNode l = len1 >= len2 ? head1 : head2;
ListNode s = l == head1 ? head2 : head1;
ListNode curL = l;
ListNode curS = s;
ListNode last = curL;
int carry = 0;
int curNum = 0;
while (curS != null) {
curNum = curL.val + curS.val + carry;
curL.val = (curNum % 10);
carry = curNum / 10;
last = curL;
curL = curL.next;
curS = curS.next;
}
while (curL != null) {
curNum = curL.val + carry;
curL.val = (curNum % 10);
carry = curNum / 10;
last = curL;
curL = curL.next;
}
if (carry != 0) {
last.next = new ListNode(1);
}
return l;
}
// 求链表长度
public static int listLength(ListNode head) {
int len = 0;
while (head != null) {
len++;
head = head.next;
}
return len;
}
}
25. K 个一组翻转链表
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode start = head;
ListNode end = getKGroupEnd(start, k);
if (end == null) {
return head;
}
// 第一组凑齐了！
head = end;
reverse(start, end);
// 上一组的结尾节点
ListNode lastEnd = start;
while (lastEnd.next != null) {
start = lastEnd.next;
end = getKGroupEnd(start, k);
if (end == null) {
return head;
}
reverse(start, end);
lastEnd.next = end;
lastEnd = start;
}
return head;
}
public static ListNode getKGroupEnd(ListNode start, int k) {
while (--k != 0 && start != null) {
start = start.next;
}
return start;
}
public static void reverse(ListNode start, ListNode end) {
end = end.next;
ListNode pre = null;
ListNode cur = start;
ListNode next = null;
while (cur != end) {
next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
start.next = end;
}
}
26. 删除有序数组中的重复项
class Solution {
public int removeDuplicates(int[] nums) {
int n = nums.length;
if (n == 0) {
return 0;
}
int fast = 1, slow = 1;
while (fast < n) {
if (nums[fast] != nums[fast - 1]) {
nums[slow] = nums[fast];
++slow;
}
++fast;
}
return slow;
}
}
若有收获，就点个赞吧
0 人点赞
