如何根据值创建有序双向链表
package clwAhu;
import java.util.Scanner;
public class DoubleLinkListDemo {
public static void main(String[] args) {
DoubleLinkList linkList = new DoubleLinkList();
linkList.add(2);
linkList.add(1);
linkList.add(3);
Node head = linkList.getHead();
showLinkList(head);
setHeadNodeLength(head);
System.out.println("链表的长度为" + head.val);
Scanner scanner = new Scanner(System.in);
System.out.print("输入带查找的值:");
int val = scanner.nextInt();
System.out.println("带查找的节点为" + searchNode(head, val));
}
/**
* 根据链表的头节点和给定的值查找节点
*
* @param head 链表的头节点
* @param val 待查找的值
* @return 如果存在,返回节点,不存在返回null
*/
public static Node searchNode(Node head, int val) {
Node curr = head.next;
while (curr != null) {
if (curr.val == val) {
return curr;
}
curr = curr.next;
}
return null;
}
/*遍历双向链表*/
public static void showLinkList(Node head) {
Node temp = head.next;
while (temp != null) {
System.out.println(temp);
temp = temp.next;
}
}
/**
* 得到链表的长度
*
* @param head 链表的头节点
* @return 返回链表的长度
*/
public static int getLinkListLength(Node head) {
int len = 0;
Node temp = head;
while (temp.next != null) {
len++;
temp = temp.next;
}
return len;
}
/**
* 头节点的值存放链表的长度
*
* @param head 链表的头节点
*/
public static void setHeadNodeLength(Node head) {
head.val = getLinkListLength(head);
}
}
class DoubleLinkList {
// 头节点中存放链表的长度
public Node head = new Node(-1);
/**
* 构造有序双向链表
*
* @param val 节点值
*/
public void add(int val) {
Node node = new Node(val);
if (head.next == null) {
node.prev = head;
head.next = node;
} else {
Node curr = head;
while (curr.next != null && curr.next.val < val) {
curr = curr.next;
}
if (curr.next != null) {
node.next = curr.next;
curr.next.prev = node;
}
node.prev = curr;
curr.next = node;
}
}
/**
* 返回头节点
*
* @return 返回头节点
*/
public Node getHead() {
return head;
}
}
class Node {
int val;
Node prev;
Node next;
public Node(int val) {
this.val = val;
}
@Override
public String toString() {
return "Node{" +
"val=" + val +
'}';
}
}