``
//结点类
public class Node {
public int data;
public Node next;
public Node() {
}
public Node(int value) {
this.data = value;
}
}
public class LinkTest {
public static void main(String[] args) {
// 创建头结点
Node head = new Node(1);
addNode(head, 12);
addNode(head, 20);
addNode(head, 18);
addNode(head, 17);
addNode(head, 47);
toPrintln(head);
System.out.println("链表长度为:" + count(head));
// deleteNode(head, 2);
deleteValue(head, 20);
updateNode(head, 18, 110);
toPrintln(head);
System.out.println("链表长度为:" + count(head));
Node h = reverseList(head);
toPrintln(h);
clcyle(h);
toPrintln(h);
}
// 增加结点
public static void addNode(Node head, int value) {
if (head == null) {
return;
}
Node newNode = new Node(value);
while (head.next != null) {
head = head.next;
}
head.next = newNode;
}
// 根据位置删除结点
public static void deleteNode(Node head, int index) {
// 插入位置不能小于0和长度大约链表长度
if (index <= 0 && index > count(head)) {
return;
}
Node cur = head;
// 删除头结点
if (index < 2 && index > 0) {
cur.data = cur.next.data;
cur.next = cur.next.next;
return;
}
// 非头结点
int j = 0;
while (cur != null && j < index - 2) {
cur = cur.next;
j++;
}
cur.next = cur.next.next;
}
// 根据值删除结点
public static void deleteValue(Node head, int value) {
Node current = head;
if (current.data == value) {
current.data = current.next.data;
current.next = current.next.next;
return;
}
while (current.next != null) {
if (current.next.data == value) {
current.next = current.next.next;
break;
}
current = current.next;
}
}
// 计算链表长度
public static int count(Node head) {
Node temp = head;
int length = 0;
while (temp != null) {
length++;
temp = temp.next;
}
return length;
}
// 修改链表值
public static void updateNode(Node head, int oldData, int newData) {
Node temp = head;
while (temp != null) {
if (temp.data == oldData) {
temp.data = newData;
}
temp = temp.next;
}
}
// 打印链表
public static void toPrintln(Node head) {
Node temp = head;
while (temp != null) {
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
System.out.println("value:" + temp.data);
temp = temp.next;
}
System.out.println("---------------------------");
}
public static void clcyle(Node head) {
Node temp=head;
for(int i=0;i<count(head)-1;i++) {
temp=temp.next;
}
temp.next=head;
}
// 链表翻转
public static Node reverseList(Node pHead) {
Node pReversedHead = null; // 反转过后的单链表存储头结点
Node pNode = pHead; // 定义pNode指向pHead;
Node pPrev = null; // 定义存储前一个结点
while (pNode != null) {
Node pNext = pNode.next; // 定义pNext指向pNode的下一个结点
if (pNext == null) { // 如果pNode的下一个结点为空,则pNode即为结果
pReversedHead = pNode;
}
pNode.next = pPrev; // 修改pNode的指针域指向pPrev
pPrev = pNode; // 将pNode结点复制给pPrev
pNode = pNext; // 将pNode的下一个结点复制给pNode
}
return pReversedHead;
}
// 链表反序
public static Node reverseList3(Node pHead) {
if (pHead == null || pHead.next == null) { // 如果没有结点或者只有一个结点直接返回pHead
return pHead;
}
Node pNext = pHead.next; // 保存当前结点的下一结点
pHead.next = null; // 打断当前结点的指针域
Node reverseHead = reverseList3(pNext); // 递归结束时reverseHead一定是新链表的头结点
pNext.next = pHead; // 修改指针域
return reverseHead;
}
}
``
网友评论