珠海网站推广,emlog建站教程,wordpress大改动,自建网站公司编程导航算法通关村第 1关 | 链表的操作 文章目录 编程导航算法通关村第 1关 | 链表的操作单链表链表的定义初始化链表的遍历获取链表的长度链表的插入链表的节点的删除 双向链表节点的定义双向链表的定义节点的打印获取长度头部插入元素尾部插入元素链表的删除 单链表
链表的…编程导航算法通关村第 1关 | 链表的操作 文章目录 编程导航算法通关村第 1关 | 链表的操作单链表链表的定义初始化链表的遍历获取链表的长度链表的插入链表的节点的删除 双向链表节点的定义双向链表的定义节点的打印获取长度头部插入元素尾部插入元素链表的删除 单链表
链表的定义
/*** 单链表节点的定义*/
public class ListNode {public int val;public ListNode next;ListNode(int x) {val x;//这个一般作用不大写了会更加规范next null;}
}初始化 public static ListNode init(ListNode head) {int i 2;ListNode temp head;while (i 10) {ListNode listNode new ListNode(i);temp.next listNode;temp temp.next;i;}return head;}链表的遍历
/*** 遍历链表*/public static void print(ListNode head) {ListNode temp head;while (temp ! null) {System.out.println(temp.val);temp temp.next; // 向后移动指针}}获取链表的长度 /*** 获取链表的长度*/public static int getLength(ListNode head) {ListNode temp head;int length 0;while (temp ! null) {temp temp.next; // 向后移动指针length;}return length;}链表的插入
在链表的插入中我们需要考虑三种情况头结点前插入直接将newNode的next指向head然后将head指向为第一个节点newNode newNode.next head;head newNode;return head;尾结点后插入:将指针指向节点的末尾 ListNode temp head;
// 先将指针移动到最后while (temp.next ! null) {temp temp.next;}temp.next newNode;return head;
中间插入需要将指针指向待插入位置的前一个节点
// 中间插入ListNode temp head;int i 1;
// 将temp移动到前一个的位置,此处的位置应该是posttion-1while (i posttion - 1) {temp temp.next;i;}
// 将新节点插入到temp之后newNode.next temp.next;temp.next newNode;return head;完整代码 /*** 插入链表 postition的范围是1——length*/public static ListNode insert(ListNode head, ListNode newNode, int posttion) {
// 分为三种情况进行讨论
// 判断参数是否合法if (head null) {return null;}if (newNode null) {return null;}int length getLength(head);if (posttion 0 || posttion length) {return null;}// 头部插入if (posttion 1) {newNode.next head;head newNode;return head;}
// 尾部插入if (posttion length) {ListNode temp head;
// 先将指针移动到最后while (temp.next ! null) {temp temp.next;}temp.next newNode;return head;}
// 中间插入ListNode temp head;int i 1;
// 将temp移动到前一个的位置,此处的位置应该是posttion-1while (i posttion - 1) {temp temp.next;i;}
// 将新节点插入到temp之后newNode.next temp.next;temp.next newNode;return head;} 链表的节点的删除
需要考虑三种情况 节点是头节点节点是尾节点节点是中间节点 /*** 单链表的删除*/public static ListNode delete(ListNode head, int posttion) {
//if (head null) {return null;}if (posttion 0 || posttion getLength(head)) {return null;}// 删除头结点if (posttion 1) {head head.next;return head;}
// 尾结点if (posttion getLength(head)) {ListNode temp head;while (temp.next.next ! null) {temp temp.next;}temp.next null;
//return head;}// 删除中间节点ListNode temp head;int i 1;
// 移动到前一个while (i posttion - 1) {temp temp.next;i;}// 删除他的下一个节点temp.next temp.next.next;return head;}双向链表
节点的定义
package com.lmx.project.first.bronze;class DoubleNode {public int data; //数据域public DoubleNode next; //指向下一个结点public DoubleNode prev;public DoubleNode(int data) {this.data data;}//打印结点的数据域public void displayNode() {System.out.print({ data } );}
}
双向链表的定义
需要定义头结点、尾结点 private DoubleNode first; // 头结点private DoubleNode last; // 尾结点public DoublyLinkList() {first null;last first;}节点的打印 * 正序打印*/public void printOrder() {DoubleNode temp first;while (temp ! null) {temp.displayNode();temp temp.next;}}/*** 导入打印*/public void printRevereOrder() {DoubleNode temp last;while (temp ! null) {temp.displayNode();temp temp.prev;}}获取长度 /*** 获取链表长度*/public int getLength() {int length 0;DoubleNode temp first;while (temp ! null) {length;temp temp.next;}return length;}头部插入元素 /*** 头部插入元素*/public void insertFirst(int data) {DoubleNode newNode new DoubleNode(data);
// 没有头结点的情况if (first null) {first newNode;last first;return;}newNode.next first;first.prev newNode;first newNode;}尾部插入元素 /*** 尾插入元素*/public void insertLast(int data) {DoubleNode newNode new DoubleNode(data);if (first null) {first newNode;last first;return;}newNode.prev last;last.next newNode;last newNode;}中间插入元素 /*** 中间插入元素*/public void insert(int data, int position) {int length getLength();if (position 0 || position length) {return;}if (position 1) {insertFirst(data);return;}if (position length 1) {insertLast(data);return;}DoubleNode newNode new DoubleNode(data);
// 中间的插入DoubleNode temp first;int i 1;while (i position - 1) {temp temp.next;i;}
// 将结点插入到temp后面temp.next.prev newNode;newNode.next temp.next;temp.next newNode;newNode.prev temp;}链表的删除 /*** 链表的删除*/public DoubleNode delete(int key) {
//DoubleNode temp first;while (temp ! null temp.data ! key) {temp temp.next;}if (temp null) {return temp;}
// 如果是头结点if (temp first) {first first.next;first.prev null;} else if (temp last) {// 如果是尾结点last.prev.next null;} else {// 如果是中间节点temp.next.prev temp.prev;temp.prev.next temp.next;temp.next null;temp.prev null;}return temp;}
