单链表反转

川长思鸟来 2023-06-25 06:01 2阅读 0赞

常常面试我们会遇到考察列表反转的问题

如 1-->2-->3-->4-->5-->null这样的一个链表进行反转成为

null<--1<--2<--3<--4<--5

/**
     * @description 链表节点
     * @date 2019/12/25 16:23
     * @version: 1.0
     **/
    public class LinkedNode<E> {
    
        public E e;
        public LinkedNode<E> next;
    
        LinkedNode(E e) {
            this.e = e;
            this.next = null;
        }
    
        LinkedNode(E e, LinkedNode<E> next) {
            this.e = e;
            this.next = next;
        }
    }

/**
     * @description 链表反转
     * @date 2019/12/25 15:15
     * @version: 1.0
     **/
    public class LinkedListReverse<E> {
    
        /**
         * 1-->2-->3-->4-->5-->6-->null
         * null<--1<--2<--3<--4<--5<--6
         * @param node
         */
        public LinkedNode<E> reverse(LinkedNode<E> head) {
            if(head == null || head.next == null) {
                return null;
            }
    
            //当前节点指针
            LinkedNode<E> cur = head;
            //前一个节点指针
            LinkedNode<E> preNode = null;
            //下一个节点指针
            LinkedNode<E> nextNode = null;
    
            while (null != cur) {
                nextNode = cur.next;
                cur.next = preNode;
                preNode = cur;
                cur = nextNode;
            }
    
            return preNode;
        }
    
    
    
        public static void main(String[] args) {
            LinkedListReverse<Integer> listReverse = new LinkedListReverse<>();
    
            Integer[] arr = {1,2,3,4,5,6};
            LinkedNode<Integer> head = new LinkedNode<>(arr[0]);
            LinkedNode<Integer> cur = head;
            for (int i=1; i < arr.length; i++) {
                LinkedNode<Integer> node = new LinkedNode<>(arr[i]);
                cur.next = node;
                cur = node;
            }
            printLinkedList(head);
    
            LinkedNode<Integer> reverseLinkedHeadNode = listReverse.reverse(head);
            printLinkedList(reverseLinkedHeadNode);
    
        }
    
        private static void printLinkedList(LinkedNode<Integer> head) {
            StringBuilder builder = new StringBuilder();
            while(head != null) {
                builder.append(head.e + " --> ");
                head = head.next;
            }
            builder.append(" NULL");
    
            System.out.println(builder.toString());
        }
    }

执行结果：

1 --> 2 --> 3 --> 4 --> 5 --> 6 -->  NULL
    6 --> 5 --> 4 --> 3 --> 2 --> 1 -->  NULL

有问题欢迎讨论