数据结构——链表的增删查改Java

``
//结点类
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;
}

}

最后编辑于：2020.06.10 17:44:07