单链表的反转java实现

阳光穿透心脏的1/2处 2022-12-27 06:30 135阅读 0赞

单链表里面的节点知道下一个节点是谁，但是无法知道上一个节点是谁，所以有的时候会需要将单链表反转过来。下面是单链表反转的java实现.

public class LinkedList {
    
        /**
         * 头节点
         */
        private Node head;
    
        /**
         * 尾节点
         */
        private Node tail;
    
        /**
         * 链表是否为空
         */
        private boolean isEmpty;
    
        public LinkedList() {
            this.isEmpty = true;
        }
    
        /**
         * 向单链表中插入数据
         * @param data
         */
        public void insert(int data){
            Node newNode = new Node(data, null);
            if(this.isEmpty){
                head = newNode;
            }else {
                tail.next = newNode;
            }
            tail = newNode;
            this.isEmpty = false;
        }
    
        /**
         * 单链表的遍历
         */
        public void traversal(){
            if(this.isEmpty){
                return;
            }
            Node current = head;
            while (current != null){
                System.out.println(current.data);
                current = current.next;
            }
        }
    
        /**
         * 节点类
         */
        private class Node{
            private int data;
    
            private Node next;
    
            public Node(int data, Node next) {
                this.data = data;
                this.next = next;
            }
    
            public int getData() {
                return data;
            }
    
            public Node setData(int data) {
                this.data = data;
                return this;
            }
    
            public Node getNext() {
                return next;
            }
    
            public Node setNext(Node next) {
                this.next = next;
                return this;
            }
        }
    
        public static void main(String[] args) {
            LinkedList linkedList = new LinkedList();
            linkedList.insert(1);
            linkedList.insert(2);
            linkedList.insert(3);
            linkedList.insert(4);
            linkedList.insert(5);
            linkedList.traversal();
            linkedList.reverse();
            linkedList.traversal();
        }
    
        /**
         * 单链表反转
         */
        public void reverse(){
            if(head == tail){
                return;
            }
            Node prev = head;
            Node pcur = prev.next;
            while (pcur != null){
                prev.next = pcur.next;
                pcur.next = head;
                head = pcur;
                pcur = prev.next;
            }
            tail = prev;
        }
    
    
    }

整体思路就是两个指针，再加一个头节点.