反转单链表（迭代+递归）-蒲公英云

反转单链表（迭代+递归）

电玩女神 2021-06-10 20:38 500阅读 0赞

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzk2ODYxMw_size_16_color_FFFFFF_t_70

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next==null) return head;
        ListNode p = head;
        ListNode q = head.next;
        ListNode m;
        p.next = null;
        while(q!=null){
            m=q.next; //记录下一个位置
            q.next=p; //断开连接
            p=q; //p作为头结点
            q=m; //q后移
        }
        return p;
    }
}

迭代的思路：

1、如果链表为null，或者只有一个结点，直接返回；

2、如果有两个及以上节点，首先定位头结点，和第二个结点，头结点的next=null，当下一个结点非null时，循环。首先把q的下一个位置记录到m，（不记录的话原链表就丢了），q结点的next连到p前面，再把p向前移一位，最后q也后移。

其实就是两个链表的思路，把原链表的元素从头开始一个个断开加到另一个链表的头部。

别人写的递归思路：

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode p = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return p;
    }
}

看起来有点难懂，看下面这个会清楚一点！

class Solution {
    public ListNode reverseList(ListNode head) {
         if (head == null || head.next == null)
             return head;
          ListNode newHead = reverseList(head.next);//整体思维，宏观语义
          ListNode temp = head.next;//保存下一个节点
          temp.next = head;//连上头与递归部分
          head.next = null;//调整尾部
          return newHead;//返回头节点
    }
}