/**
* 单链表
*/
class Node{
public int data;
public Node next;
public Node(int data){
this.data = data;
this.next = null;
}
}
public class MyLinkedList {
public Node head;//保存头节点的引用
// 1、无头单向非循环链表实现---------------------------------------------------------
//头插法
public void addFirst(int data){
Node node = new Node(data);//有了一个节点
if (this.head == null){
//第一次插入节点
this.head = node;
return;
}
node.next = this.head;
this.head = node;
}
//尾插法
public void addLast(int data){
Node node = new Node(data);
Node cur = this.head;
if (cur == null){
this.head = node;
return;
}
while (cur.next != null){
cur = cur.next;
}
cur.next = node;
}
//2.任意位置插入,第一个数据节点为0号下标-------------------------------------------------
public void addIndex(int index,int data){
Node node = new Node(data);
if (index == 0){
addFirst(data);
return ;
}
if (index == this.size()){
addLast(data);
return;
}
Node cur = searchIndex(index);
node.next = cur.next;
cur.next = node;
}
private Node searchIndex(int index){
if (index < 0 || index > this.size()){
throw new RuntimeException("index位置不合法");
}
Node cur = this.head;
while (index - 1 != 0){
cur = cur.next;
index--;
}
return cur;
}
//查找是否包含关键字key是否在单链表当中-------------------------------------------------------
public boolean contains(int key){
Node cur = this.head;
while (cur != null){
if (cur.data == key){
return true;
}
cur = cur.next;
}
return false;
}
//删除第一次出现关键字为key的节点------------------------------------------------------------
public void remove(int key){
if (this.head == null){
return;
}
//如果是头节点，直接删除
if (this.head.data == key){
this.head = this.head.next;
}
Node prev = findPast(key);
if (prev == null){
System.out.println("没有这个节点");
}
Node del = prev.next;
prev.next = del.next;
}
//找目标节点的前一个节点
public Node findPast(int key){
Node prev = this.head;
while (prev.next != null){
if(prev.next.data == key){
return prev;
}
}
return null;
}
//删除所有值为key的节点------------------------------------------------------------------
public void removeAllKey(int key){
Node prev = this.head;
Node cur = prev.next;
while (cur != null){
if (cur.data == key){
prev.next = cur.next;
cur = cur.next;
}else {
prev = cur;
cur = cur.next;
}
}
//如果刚开始的头节点重复了，就删除头节点
if (this.head.data == key){
this.head = this.head.next;
}
}
//得到单链表的长度-------------------------------------------------------------------
public int size(){
int count = 0;
Node cur = this.head;
while (cur != null){
count++;
cur = cur.next;
}
return count;
}
//打印------------------------------------------------------------------------------
public void display(){
Node cur = this.head;
while (cur != null){
System.out.print(cur.data + " ");
cur = cur.next;
}
}
public void clear(){
this.head = null;
}
}
主函数
public static void main(String[] args) {
MyArrayList myArrayList = new MyArrayList();
myArrayList.add(0,0);
myArrayList.add(1,1);
myArrayList.add(2,2);
myArrayList.add(3,3);
myArrayList.add(4,4);
myArrayList.add(5,5);
myArrayList.add(6,6);
// 也可以这样赋值：
// for (int i = 0; i < 10; i++){
// myArrayList.add(i, i);
// }
myArrayList.add(7,19);
myArrayList.display();
System.out.println(myArrayList.search(19));
System.out.println(myArrayList.getPos(5));
myArrayList.setPos(2,64);
myArrayList.display();
}
相关练习题如下
class ListNode {
public int val;
public ListNode next;
public ListNode(int val){
this.val = val;
this.next = null;
}
}
public class TestDemo1025_1 {
public ListNode head;
//给定一个头结点为 head 的非空单链表，返回链表的中间结点。
//
//如果有两个中间结点，则返回第二个中间结点。
//
//
public ListNode middleNode() {
ListNode fast = this.head;
ListNode slow = this.head;
while (fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
//链表中倒数第k个节点
public ListNode findLastK(int k){
if (k <= 0 ){
System.out.println("不合法");
return null;
}
ListNode fast = this.head;
ListNode slow = this.head;
while (k-1 != 0){
if (fast.next != null){
fast = fast.next;
k--;
}else {
System.out.println("没有这个节点");
return null;
}
}
while (fast.next != null){
slow = slow.next;
fast = fast.next;
}
return slow;
}
//现有一链表的头指针 ListNode* pHead，给一定值x，
// 编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
public ListNode partition(int x){
ListNode bs = null;
ListNode be = null;
ListNode as = null;
ListNode ae = null;
ListNode cur = this.head;
while (cur != null) {
if (cur.val < x){
//第一次插入
if (bs == null){
bs = cur;
be = bs;
}else {
be.next = cur;
be = be.next;
}
}else {
//第一次插入
if (as == null){
as = cur;
ae = as;
}else {
ae.next = cur;
ae = ae.next;
}
}
cur = cur.next;
}
//1.判断bs是否为空，如果为空，返回as
if (bs == null){
return as;
}
//2.如果bs不为空，需要进行拼接
be.next = as;
//3.如果ae不为空，则需要吧ae.next置为空
if (ae != null){
ae.next = null;
}
return bs;
}
//在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。
// 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
public ListNode deleteDuplication(ListNode pHead) {
ListNode cur = this.head;
ListNode newHead = new ListNode(-1);
ListNode tmp = newHead;
while (cur != null){
if (cur.next != null && cur.val == cur.next.val){
while (cur.next != null && cur.val == cur.next.val){
cur = cur.next;
}
cur = cur.next;
}else {
tmp.next = cur;
tmp = tmp.next;
cur = cur.next;
}
}
tmp.next = null;
return newHead.next;
}
//反转单链表
public ListNode change(){
ListNode prev = null;
ListNode cur = this.head;
ListNode curNext = null;
ListNode newHead = null;
while (cur != null){
curNext = cur.next;
if (curNext == null){
newHead = cur;
}
cur.next = prev;
prev = cur;
cur = curNext;
}
return newHead;
}
//对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
//
//给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
//
//测试样例：
//1->2->2->1
//返回：true
public boolean chkPalindrome() {
// write code here
ListNode fast = this.head;
ListNode slow = this.head;
if (this.head == null){
return false;
}
if (this.head.next == null){
//只有头节点自己，必然是回文
return true;
}
//找到中间
while (fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
//反转后半段
ListNode cur =slow.next;
while (cur != null){
ListNode curNext = cur.next;
cur.next = slow;
slow = cur;
cur = curNext.next;
}
//此时slow是最后一个了
while (slow != this.head){
if (this.head.val != slow.val){
return false;
}
if (this.head.next == slow){
return true;
}
slow = slow.next;
this.head = this.head.next;
}
return true;
}
}