16_反转链表

柔光的暖阳◎ 2022-06-07 01:38 140阅读 0赞

> 题目：输入一个链表的头结点，反转该链表并输出反转后链表的头结点。

import java.util.Scanner;
    
    class ListNode{
        int value;
        ListNode next;
    }
    
    public class Main{
        //递归反转
        private static ListNode reverse1(ListNode head) {
            if(head == null || head.next == null)
                return head;
            ListNode nextNode = head.next;
            head.next = null;
            ListNode reverseRest = reverse1(nextNode);
            nextNode.next = head;       
            return reverseRest;
        }
    
        //遍历反转
        private static ListNode reverse2(ListNode cur) {
            if(cur == null || cur.next == null)
                return cur;     
            ListNode pre = null;// 上一结点
            ListNode nextNode = null;// 下一结点
            // 当前结点为null，说明位于尾结点
            while(cur != null){
                nextNode = cur.next;
                cur.next = pre;// 反转指针域的指向 
    
                // 指针往下移动
                pre = cur;
                cur = nextNode;
            }
            return pre;
        }
    
        private static void printReverseList(ListNode head){
            ListNode tempNode = head;
            while(tempNode != null){
                System.out.print(tempNode.value +" ");
                tempNode = tempNode.next;
            }
        }
    
        public static void main(String[] args) {
            System.out.print("请输入单链表的节点数：");
            Scanner in = new Scanner(System.in);
            while (in.hasNext()) {      
                ListNode node = new ListNode();
                ListNode node1 = node;//用于输出原链表
                ListNode node2 = node;//用于输出递归反转后的链表
                ListNode node3 = node;//用于输出遍历反转后的链表
                node.next = null;
                int N = in.nextInt();//链表结点个数
                if(N <= 0)
                    return;
                System.out.print("请输入链表(以空格隔开)：");
                for (int i = 0; i < N; i++) {
                    ListNode p = new ListNode();
                    p.value = in.nextInt();
                    p.next = null;
                    node.next = p;
                    node = node.next;
                }       
    
                System.out.print("原链表：");
                printReverseList(node1.next);
                System.out.println();
    
                System.out.print("递归输出：");
                printReverseList(reverse1(node2.next));
                System.out.println();
    
                //System.out.print("遍历输出：");
                //printReverseList(reverse2(node3.next));
            }
            in.close();
        }
    }

![这里写图片描述][SouthEast]

![这里写图片描述][SouthEast 1]

![这里写图片描述][SouthEast 2]

[SouthEast]: /images/20220607/f6ddc64d43cc403389762d56a1a3c74c.png
[SouthEast 1]: /images/20220607/2cfbdd91f49049c39b72e14516cb3496.png
[SouthEast 2]: /images/20220607/1f04d72cd1f645ce8d77ebcfe2932f3d.png