数据结构和算法之单链表

package com.company;import java.util.Stack;/*** @author:抱着鱼睡觉的喵喵* @date:2021/2/4* @description:*/
public class LinkedListDemo {//test模块public static void main(String[] args) {Node node4 = new Node(4, 96, "Ronin");Node node1 = new Node(2, 100, "lisi");Node node2 = new Node(1, 99, "张三");Node node3 = new Node(3, 63, "zsh");Node node5 = new Node(5, 65, "zms");SingleLinkedList singleLinkedList = new SingleLinkedList();SingleLinkedList singleLinkedList2 = new SingleLinkedList();
//        singleLinkedList.add(node1);
//        singleLinkedList.add(node2);singleLinkedList.insert(node4);singleLinkedList.insert(node1);singleLinkedList.insert(node2);singleLinkedList2.insert(node3);singleLinkedList2.insert(node5);mergeLinkedList2(singleLinkedList,singleLinkedList2);int num1 = getLength(singleLinkedList.getNode());int num2 = getLength(singleLinkedList2.getNode());if (num1 >= num2) {singleLinkedList.list();} else {singleLinkedList2.list();}//        singleLinkedList.delete(5);//        System.out.println(getLength(singleLinkedList.getNode()));
//        System.out.println(getReciprocalNode1(singleLinkedList.getNode(),2));
//        System.out.println("链表反转后的数据如下:");
//        getReverse2(singleLinkedList.getNode());
//        singleLinkedList.list();
//        stackPrint(singleLinkedList.getNode());}//计算链表长度public static int getLength(Node node) {if (node.next == null) {return 0;}int length = 0;Node cur = node.next;while (cur != null) {length++;cur = cur.next;}return length;}/*** 计算链表倒数k个节点的数据* 思路：1.计算链表总长度* 2.倒数第k个数据，也就是正数第length-k+1个数据* 3.遍历链表到第length-k+1个数据** @param head* @param k* @return*/public static Node getReciprocalNode1(Node head, int k) {if (head.next == null) {return null;}int size = getLength(head);if (k <= 0 || k > size) {return null;}Node temp = head.next;for (int i = 0; i < (size - k); i++) {temp = temp.next;}return temp;}/*** 链表的反转 方法1* 思路：1.反转相当于数据的更换（1和n，2和n-1，3和n-2)n为链表的长度* 2.通过遍历进行数据的更换，n/2为循环退出的条件** @param head* @return*/public static void getReverse(Node head) {if (head.next == null) {System.out.println("LinkedList is empty！");return;}int length = getLength(head);int num1 = 0;int num2 = 0;Node mid = new Node();for (int i = 1, j = length; i <= length / 2; i++, j--) {Node temp = head;Node cur = head;while (true) {temp = temp.next;num1++;if (num1 == i) {num1 = 0;break;}}while (true) {cur = cur.next;num2++;if (j == num2) {num2 = 0;break;}}mid.sno = temp.sno;mid.score = temp.score;mid.data = temp.data;temp.sno = cur.sno;temp.score = cur.score;temp.data = cur.data;cur.sno = mid.sno;cur.score = mid.score;cur.data = mid.data;}Node temp2 = head.next;while (temp2 != null) {System.out.println(temp2);temp2 = temp2.next;}}/*** 链表的反转2* 思路：* 初始化一个新的头节点reverseHead，然后遍历链表head,利用头插法向reverseHead进行插入** @param head*/public static void getReverse2(Node head) {if (head.next == null) {System.out.println("LinkedList is empty！");return;}Node reverseHead = new Node(0, 0, "");Node cur = null;Node temp = head.next;while (temp != null) {cur = temp.next;temp.next = reverseHead.next;reverseHead.next = temp;temp = cur;}head.next = reverseHead.next;}/*** 单链表的逆序打印，不改变原先单链表的结构* 思路：栈** @param head 单链表的头节点*/public static void stackPrint(Node head) {if (head.next == null) {System.out.println("LinkedList is empty！");return;}Stack<Node> stack = new Stack<>();Node cur = head.next;while (cur != null) {stack.push(cur);cur = cur.next;}while (stack.size() > 0) {System.out.println(stack.pop());}}public static void mergeLinkedList(Node head1, Node head2) {Node temp = head1;int num1 = getLength(head1);int num2 = getLength(head2);if (num1 == 0 || num2 == 0) {return;}Node next = head2.next;if (num1 >= num2) {for (int i = 0; i < num2; i++) {boolean flag = false;while (true) {if (temp.next == null) {break;}if (head2.next == null) {return;}if (temp.next.sno > head2.next.sno) {break;}if (temp.next.sno == head2.next.sno) {flag = true;break;}temp = temp.next;}if (flag == true) {System.out.println("数据" + head2.next.sno + "发生了重复!");} else {next = next.next;head2.next = temp.next;temp = head2.next;head2 = next;}}}}/*** 合并两个链表，并且按照有序合并* @param singleLinkedList1 链表1* @param singleLinkedList2 链表2*/public static void mergeLinkedList2(SingleLinkedList singleLinkedList1, SingleLinkedList singleLinkedList2) {int num1 = getLength(singleLinkedList1.getNode());int num2 = getLength(singleLinkedList2.getNode());if (singleLinkedList1.getNode().next == null || singleLinkedList2.getNode().next == null) {return;}if (num1 >= num2) {Node cur = singleLinkedList2.getNode().next;Node cur2 = null;while (cur != null) {cur2 = cur.next;singleLinkedList1.insert(cur);cur = cur2;}} else {Node temp = singleLinkedList1.getNode().next;Node temp2 = null;while (temp != null) {temp2 = temp.next;singleLinkedList2.insert(singleLinkedList1.getNode());temp = temp2;}}}
}//节点类
class Node {public Node next;public int sno;public int score;public String data;public Node() {}public Node(int Sno, int NScore, String Data) {this.sno = Sno;this.score = NScore;this.data = Data;}@Overridepublic String toString() {return "Node{" +"sno=" + sno +", score=" + score +", data='" + data + '\'' +'}';}
}//链表操作类
class SingleLinkedList {private Node head = new Node(0, 0, ""); //初始化头节点public Node getNode() {return head;}// add student datapublic void add(Node node) {        //数据添加Node temp = head;while (temp.next != null) {temp = temp.next;}temp.next = node;}//outputpublic void list() {            //遍历数据进行打印Node temp = head.next;if (temp == null) {System.out.println("LinkedList is empty!");} else {while (temp != null) {System.out.println(temp);System.out.println();temp = temp.next;}}}//insert by order 1  有序插入/*  public void insert(Node node) {       //插入数据方式1 Node temp = head.next;while (temp != null) {      //determine whether the node's sno is the sameif (temp.sno == node.sno) {System.out.println("the student ID:" + node.sno + " already exists!");return;}temp = temp.next;}Node temp2 = head;Node tail = head.next;while (temp2 != null) {if (head.next == null) {    //Determine whether the inserted node is the first nodehead.next = node;break;} else if (tail.next == null) {     //determine whether the inserted node is the tail nodeif (tail.sno < node.sno) {tail.next = node;break;} else {temp2.next = node;node.next = tail;break;}} else if (tail.sno < node.sno) {       //insert according to the student snotemp2 = temp2.next;tail = tail.next;} else {                        //inserttemp2.next = node;node.next = tail;break;}}} *///insert by order 2 有序插入public void insert(Node node) {      //插入数据方式2Node temp = head;boolean flag = false;while (true) {if (temp.next == null) {break;}if (temp.next.sno > node.sno) {break;} else if (temp.next.sno == node.sno) {flag = true;break;}temp = temp.next;}if (flag) {System.out.println("Student ID ：" + node.sno + "already exists!");return;} else {node.next = temp.next;temp.next = node;}}public void modify(Node newNode) {           //修改操作Node temp = head.next;if (head.next == null) {System.out.println("LinkedList is empty,unable to modify!");return;}boolean flag = false;while (true) {if (temp == null) {break;}if (temp.sno == newNode.sno) {flag = true;break;}temp = temp.next;}if (flag) {temp.score = newNode.score;temp.data = newNode.data;} else {System.out.println("No student ID" + newNode.sno);}}public void delete(int sno) {        //删除操作Node temp = head;boolean flag = false;if (head.next == null) {System.out.println("LinkedList is empty,Unable to delete.");return;}while (true) {if (temp.next == null) {break;}if (temp.next.sno == sno) {flag = true;break;}temp = temp.next;}if (flag) {temp.next = temp.next.next;} else {System.out.println("No student ID:" + sno);}}/*** 计算链表中第倒数k个数据* 思路：1.计算链表总长度* 2.倒数第k个数据，也就是正数第length-k+1个数据* 3.遍历链表到第length-k+1个数据** @param k* @return*/public Node getReciprocalKNode2(int k) {if (head.next == null) {System.out.println("LinkedList is empty");return null;}Node temp = head.next;int num = 0;while (true) {if (temp == null) {break;}num++;temp = temp.next;}if (k > num || k <= 0) {System.out.println(k + "Has exceeded the length of the linkedList!");return null;}int dif = num - k + 1;int num2 = 0;Node cur = head.next;while (true) {num2++;if (dif == num2) {break;}cur = cur.next;}return cur;}}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！