Java反转链表

ゝ一世哀愁。 2023-10-12 21:41 115阅读 0赞

#### 给定单链表的头结点head，请你反转链表，并返回反转后的链表 ####

示例：![在这里插入图片描述][0fc3c525452842e5b7cb3a61047f8779.png]  
输入：\[1,2,3,4,5\]。输出：\[5,4,3,2,1\]

##### 方式一： #####

/**
         * 反转链表
         *
         * @param head
         * @return
         */
        public ListNode reverseList(ListNode head) {
        
            if (head == null) return head; /*当链表为空时直接返回*/
            ListNode current = head.next;/*表示当前节点*/
            head.next = null;/*翻转前为头结点，反转后就是尾结点，尾结点的next值要为null*/
            while (current != null) {
        
                ListNode currentNext = current.next;/*先提前保存一下当前结点的下一个结点*/
                current.next = head;
                head = current;
                current = currentNext;
            }
            return head;
        }
    
    
        public static class ListNode {
        
            public int value;
            public ListNode next;
    
            public ListNode(int value) {
        
                this.value = value;
            }
        }

测试翻转后的打印结果：

public static void main(String[] args) {
        
            ListNode listNode1 = new ListNode(1);
            ListNode listNode2 = new ListNode(2);
            ListNode listNode3 = new ListNode(3);
    
            listNode1.next = listNode2;
            listNode2.next = listNode3;
            listNode3.next = null;
    
            ListNode head = reverseList(listNode1);
            while (head != null) {
        
                System.out.println(head.value);
                head = head.next;
            }
        }

##### 方式二： #####

/**
         * 递归方式实现反转链表
         *
         * @param head
         * @return
         */
        public ListNode reverseListByRecursion(ListNode head) {
        
            if (head == null || head.next == null) return head;
            ListNode newHead = reverseListByRecursion(head.next);
            head.next.next = head;
            head.next = null;
            return newHead;
        }

[0fc3c525452842e5b7cb3a61047f8779.png]: https://img-blog.csdnimg.cn/0fc3c525452842e5b7cb3a61047f8779.png