反转链表

题目

方法

迭代

• 需要中间变量两个
  • 指向当前节点的下一个元素next指针
  • 指向当前节点的上一个元素prev指针

• 返回新的头结点

    //官方 
    public ListNode reverseList(ListNode head) {
         ListNode prev = null;
         ListNode curr = head;
         while (curr != null) {
             ListNode nextTemp = curr.next;
             curr.next = prev;
             prev = curr;
             curr = nextTemp;
         }
         return prev;
     }
    //自己
    public ListNode reverseList(ListNode head) {
        if (head == null) return head;
        ListNode prevNode = head;
        head = head.next;
        prevNode.next = null;
        while (head != null) {
            ListNode nextNode = head.next;
            head.next = prevNode;
            prevNode = head;
            head = nextNode;
        }
        return prevNode;
    }

• 步骤

  • 定义prev，curr变量
  • 在循环里交换节点
  • 返回新节点

    递归

• 其实就是隐式使用了栈，相当于从头开始遍历存储到栈中，然后再逐个取出来，让每个指向前一个

    //官方
    public ListNode reverseList(ListNode head) {
        //head == null判断的是第一次头结点是否为空，head.next == null是遍历到链尾时才其作用
        if (head == null || head.next == null) {
            return head;
        }
        //递归链表到最后一个节点
        ListNode p = reverseList(head.next);
        //head的下一个节点指向head自己
        head.next.next = head;
        //避免回到最初头结点时的循环
        head.next = null;
        //返回新的头结点
        return p;
    }
  
    //自己
     public ListNode reverseList(ListNode head) {
       if (head == null) return head;
       ListNode tail = recur(head);
       tail.next = null;
       return nHead;
    }
  
    private ListNode recur(ListNode head) {
        if (head.next == null) {
            this.nHead = head;
            return head;
        }
        ListNode nextNode = recur(head.next);
        nextNode.next = head;
        return head;
    }
  

• 步骤

  • 递归到链尾
  • 规定每个节点所要做的事情，反转节点
  • 返回头结点

反转链表