Java反转单链表

拼搏现实的明天。 2023-07-04 11:19 144阅读 0赞

方法：从头结点后继结点开始，依次取每个节点，利用头插法重新建立链表。

1.  取头结点后继 p，p 后继结点q，将头结点后继设为空
2.  利用头插法将 p 插入到头结点后
3.  前进 p 和 q，（p = q，q = q.next）
4.  重复步骤 2 ~ 3

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70]

import java.util.Scanner;
    
    class ListNode { 
        int val;
        ListNode next;
        ListNode(int x) {  val = x; next = null;}
    }
    
    public class LinkedListDemo { 
        private void addNode(ListNode head, ListNode node) { 
            ListNode temp = head;
    
            while (temp.next != null) { 
                temp = temp.next;
            }
            temp.next = node;
        }
    
        private void traverseLinkedList(ListNode head) { 
            ListNode temp = head;
    
            while (temp.next != null) { 
                System.out.print(temp.next.val + ", ");
                temp = temp.next;
            }
            System.out.println();
        }
    
        private ListNode reverseLinkedList(ListNode head) { 
            ListNode p = head.next;
            ListNode q = p.next;
            head.next = null;
    
            while (p.next != null) { 
                p.next = head.next;
                head.next = p;
                p = q;
                q = p.next;
            }
            p.next = head.next;
            head.next = p;
    
            return head;
        }
    
        public static void main(String[] args) { 
            Scanner scanner = new Scanner(System.in);
            LinkedListDemo demo = new LinkedListDemo();
    
            System.out.print("请输入链表节点个数：");
            int num = scanner.nextInt();
            ListNode head = new ListNode(-1);
            for (int i = 0; i < num; i++) { 
                ListNode node = new ListNode(i);
                demo.addNode(head, node);
            }
    
            System.out.print("原链表：");
            demo.traverseLinkedList(head);
    
            System.out.print("反转后的链表：");
            demo.reverseLinkedList(head);
            demo.traverseLinkedList(head);
        }
    }

请输入链表节点个数：10
    原链表：0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 
    反转后的链表：9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 
    
    Process finished with exit code 0

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200210153528546.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg==,size_16,color_FFFFFF,t_70