反转单链表

1.描述

给你单链表的头指针head ，请你反转链表，并返回反转后的链表。
如下：

2.方法一

思路分析

1）创建一个新的头指针newHead。
2）创建一个结点p遍历反转前的链表，每遍历一个结点，把newHead指向当前结点。同时创建一个结点cur，用来保存p的下一个结点，以此来保证p遍历整个反转前的链表。
3）最后原来头指针head，指向新的链表。

图示

代码

/**
 * Definition for singly-linked list.
 * public class Node {
 *     int val;
 *     Node next;
 *     Node() {}
 *     Node(int val) { this.val = val; }
 *     Node(int val, Node next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public void reverse(Node head) {
        //链表为空，或链表长度为1
        if (head == null || head.next == null) {
            return;
        }

        Node p = head;
        Node newHead;
        Node cur;

        cur = p.next;
        newHead = p;
        p.next = null;//新链表的尾结点，next域置为null
        while (cur != null) {
            p = cur;
            cur = p.next;
            p.next = newHead;
            newHead = p;
        }
        head = newHead;
    }
}

3.方法二

思路分析

把一个单链表逆转，我们直接把每个结点的next域直接指向前一个结点不就可以了吗（第一个结点的next域置为空），最后把head指向反转链表前的最后一个结点。如下：

1）设置一个结点p指向head。
2）设置一个结点q指向p的下一个结点。
3）设置一个s指向q的下一个结点。
4）头结点的next域置为null。
5）q的next域指向p。
6）因为头结点的next域已经置为null,所以把q赋值给p，来移动到下一个结点。
7）q借助s移动到下一个结点。
8）s移动到下一个结点。
9）循环操作2~8直到q为null。

图示

代码

/**
 * Definition for singly-linked list.
 * public class Node {
 *     int val;
 *     Node next;
 *     Node() {}
 *     Node(int val) { this.val = val; }
 *     Node(int val, Node next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public void reverse(Node head) {
        //链表为空或链表长度为1
        if (head == null || head.next == null) {
            return;
        }

        Node<E> p = head,q = p.next,s = q.next;
        head.next = null;//新尾巴

        while (q != null) {
            q.next = p;
            p = q;
            q = s;
            if (s != null) {
                s = s.next;
            }
        }
        head = p;//指向新头
    }
}

4.方法三

思路分析

1）创建一个新的头指针pre，初始化为null。
2）创建一个结点cur指向当前结点。
3）当前结点的next域指向pre。
4）pre借助cur指向下一个结点。
5）cur指向原来链表的下一个结点（因为第三步中cur指向的结点的next域已经更新，需要一个Cur_next结点来完成移动，cur完成移动后，Cur_next移向下一个结点）。
6）循环2~5操作，直到cur为null。
7）返回pre。

图示

代码

/**
 * Definition for singly-linked list.
 * public class Node {
 *     int val;
 *     Node next;
 *     Node() {}
 *     Node(int val) { this.val = val; }
 *     Node(int val, Node next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
     public Node ReverseList(Node head) {
        //链表为空或链表长度为1
        if(head == null || head.next == null) {
            return null;
        }
         
        Node pre = null;//pre指针：用来指向反转后的节点，初始化为null 
        Node cur = head; //当前节点指针
        
        //循环迭代
        while(cur != null) {
            //Cur_next 节点，永远指向当前节点cur的下一个节点
            Node Cur_next = cur.next;
            //反转的关键：当前的节点指向其前一个节点
            cur.next = pre;
             //更新pre
            pre = cur;
            //更新当前节点指针
            cur = Cur_next;
        }
        return pre;
    }
}