面试准备（八）链表反转

红太狼 2022-10-12 13:57 114阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNzcxNTY3_size_16_color_FFFFFF_t_70][]

**解题思路一：**

![20210705102719772.png][]

链表指向的都是下一个元素的指针，如果想链表反转，需要使用一个变量保存一下下一个元素的指针。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNzcxNTY3_size_16_color_FFFFFF_t_70 1][]

每一次处理结果作为下一次处理的初始值。

**解题思路二：**

**递归思想**

大问题拆成小问题，必须从最后一个元素开始才能保证链表不断。

**代码：**

public class ReverseList {
        //内部链表类
        static class ListNode{
            int val;
            ListNode next;
    
            public ListNode(int val, ListNode next){
                this.val = val;
                this.next = next;
            }
    
            //迭代
            public static ListNode iterate(ListNode head){
                //定义前一个元素以及后一个
                ListNode prev=null, next;
                ListNode curr = head;
                while(curr!=null){
                    next = curr.next;
                    curr.next = prev;
                    prev = curr;
                    curr = next;
                }
                return prev;
            }
            //递归
            public static ListNode recursion(ListNode head){
                if(head==null || head.next==null){
                    return head;
                }
                ListNode res_head = recursion(head.next);
                head.next.next = head;
                head.next = null;
                return res_head;
            }
        }
    
    
    
        public static void main(String[] args) {
            ListNode node5 = new ListNode(5, null);
            ListNode node4 = new ListNode(4, node5);
            ListNode node3 = new ListNode(3, node4);
            ListNode node2 = new ListNode(2, node3);
            ListNode node1 = new ListNode(1, node2);
    
            //System.out.println(ListNode.iterate(node1).val);
    
            System.out.println(ListNode.recursion(node1).val);
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNzcxNTY3_size_16_color_FFFFFF_t_70]: /images/20221005/57c0f3f08ab04744ba7055684e2ec908.png
[20210705102719772.png]: /images/20221005/3ca69a53f6b24ed4b73fa800244b37ef.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNzcxNTY3_size_16_color_FFFFFF_t_70 1]: /images/20221005/a0e1c67be92744da9624f2f856e76a30.png