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

电玩女神 2021-06-10 20:38 384阅读 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;//返回头节点
        }
    }

### 递归思路： ###

1、把大小为5的链表可以看成1个+4个，4个可以看成1个+3个的想法，递归的出口就是最后一个元素，head.next==null;

2、首先我们ListNode newHead = reverseList(head.next);定义反转后新链表的头结点，函数里面要解决的就是  头结点 + 尾结点 的反转，首先先记录 尾结点为temp；尾结点的下一个连到头结点，头结点下一个指向null，返回新的头结点。

还是有点难理解的，局部整理的思维

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzk2ODYxMw_size_16_color_FFFFFF_t_70]: /images/20210518/0638662b4aff45b68124072342ae0c3e.png