java实现链表及其相关操作

2019-11-06 06:22:39

字体：大中小

来源：转载

供稿：网友

java实现链表及其相关操作，如下所示：

头插法尾插法遍历倒置在有序的链表中插入一个数还是有序在有序的链表中删除一个数还是有序合并两个有序列表

Node文件代码如下：

public class Node { Object data; Node next; public Object getData() { return data; } public void setData(int data) { this.data = data; } public Node() { // TODO Auto-generated constructor stub this.data = null; } public Node(int data) { // TODO Auto-generated constructor stub this.data = data; } /** * 头插法建立链表 * @param length 链表的长度，这里先设定初始长度 * @return 链表的头指针 */ public Node createListF(int length) { Node head,s; head = new Node(); head.next = null; for (int i=1; i<=length; i++) { s = new Node(i); s.next = head.next; head.next = s; } return head; } /** * 尾插法建立链表 * @param length 链表的长度，这里先设定初始长度 * @return 链表的头指针 */ public Node createListR(int length) { Node head,rear,s; head = new Node(); rear = head; for (int i=1; i<=length; i++) { s = new Node(i); rear.next = s; rear = s; } rear.next = null; return head; } public void traverseList(Node head) { Node p = head.next; while(p != null) { System.out.PRint(p.data + " "); p = p.next; } System.out.println(); } /** * 链表反转 * @param head 反转前链表的头指针 * @return head 反转后链表的头指针 */ public Node reverseList(Node head) { Node p,q,temp; p = head.next; q = p.next; while (q != null) { temp = q.next; q.next = p; p = q; q = temp; } head.next.next = null; head.next = p; return head; } /** * 在有序的链表中插入一个数还是有序 * @param head 插入前链表的头指针 * @param x 要插入的值 * @param asc 初始链表是否升序 * @return head 插入后链表的头指针 */ public Node insertDataInOrderedList(Node head,int x,boolean asc) { Node p,s,q; q = head; p = q.next; if (asc) { //升序 while ((p != null) && (Integer.parseInt(p.data == null?"":p.data.toString())) <= x) { q = p; p = p.next; } s = new Node(x); q.next = s; s.next = p; p = null; q = null; } else { while ((p != null) && (Integer.parseInt(p.data == null?"":p.data.toString())) >= x) { p = p.next; q = q.next; } s = new Node(x); q.next = s; s.next = p; p = null; q = null; } return head; } /** * 在有序的链表中删除一个数还是有序 * @param head * @param x * @param asc * @return */ public boolean deleteDataInOrderedList(Node head, int x,boolean asc) { Node p,q; q = head; p = q.next; while ((p != null) && (Integer.parseInt(p.data == null?"":p.data.toString())) != x) { q = p; p = p.next; } if(p == null) { return false; } q.next = p.next; p = null; q = null; return true; } /** * 合并两个有序列表 * @param head1 * @param head2 * @return */ public Node mergeTwoOrderedList(Node head1,Node head2) { Node head,p1 = head1.next,p2 = head2.next; //p1,p2分别为head1,head2的游标 head = new Node(); //生成头结点 head.next = null; while (p1 != null && p2 != null) { if (objToInt(p1.data) <= objToInt(p2.data)) { head.addNodeAtTheEnd(head, objToInt(p1.data)); p1 = p1.next; } else { head.addNodeAtTheEnd(head, objToInt(p2.data)); p2 = p2.next; } } while(p1 != null) { head.addNodeAtTheEnd(head, objToInt(p1.data)); p1 = p1.next; } while(p2 != null) { head.addNodeAtTheEnd(head, objToInt(p2.data)); p2 = p2.next; } return head; } /** * 在链表的末端追加元素 * @param head 原来链表的头指针 * @param x 所追加元素的值 * @return head 追加元素之后的链表的头指针 */ public Node addNodeAtTheEnd(Node head,int x) { Node q = head,p = q.next; while (p != null) { q = p; p = p.next; } Node newNode = new Node(x); q.next = newNode; newNode.next = null; return head; } /** * Object转化为int * @param obj * @return */ public int objToInt(Object obj) { return Integer.parseInt(obj == null ? "" : obj.toString()); }}

Test文件代码如下：

public class Test { public static void main(String[] args) { Node node = new Node(); Node head = node.createListF(6); System.out.print("头插法建立的链表:"); node.traverseList(head); System.out.print("反转后的链表:"); head = node.reverseList(head); node.traverseList(head); System.out.print("插入值为4的数之后的链表:"); head = node.insertDataInOrderedList(head, 4, true); node.traverseList(head); System.out.print("删除链表中第一个值为5的数，是否成功？"); boolean isDeleted = node.deleteDataInOrderedList(head, 5, true); if (isDeleted) { System.out.print("已被删除！"); System.out.println(); } System.out.print("删除链表中第一个值为5的数之后的链表:"); node.traverseList(head); System.out.print("新增值为10的结点:"); node.addNodeAtTheEnd(head, 10); node.traverseList(head); Node newHead = node.createListR(10); System.out.print("原来的head链表:"); node.traverseList(head); System.out.print("原来的newHead链表:"); node.traverseList(newHead); Node mergeNode = node.mergeTwoOrderedList(head, newHead); System.out.println("Merge two linklist:"); node.traverseList(mergeNode); }}

小白所写，有错误请指出。

上一篇：IntelliJ编译时，致命错误：在路径和启动路径中找不到包java.lang

下一篇：[java] 快速排序