反转链表-剑指Offer（Java语言）

题目描述

输入一个链表，反转链表后，输出新链表的表头。

思路

方法一：递归

写一个递归方法，返回值为反转后的链表的头结点（即反转之前的尾结点）

步骤为：

1. 反转除头结点head外，剩余结点组成的链表的反转链表，并返回反转链表的头结点t
2. 此时要做的就是将head加到反转链表的末尾。已知head.next为剩余结点组成的链表的头结点，即剩余结点组成的链表的反转链表的尾结点，故将head连接到head.next结点后即可。然后将head的next指向空
3. 返回反转链表头结点t

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

方法二

可以将结点都先入栈，然后出栈连接起来

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
import java.util.Stack;
public class Solution {
    public ListNode ReverseList(ListNode head) {
        Stack<ListNode> s=new Stack<>();
        while(head!=null){
            s.push(head);
            head=head.next;
        }
        ListNode root=null;
        if(!s.isEmpty()) {
            root=s.pop();
        }
        ListNode t=root;//t来保存上一个结点，因为要让上一个结点的next指向当前要出栈的结点
        while(!s.isEmpty()){
            ListNode m=s.pop();
            t.next=m;
            t=m;
        }
        if(t!=null) t.next=null;
        return root;
    }
}

方法三：非递归

使用三个引用pre,head,next分别指向当前结点的前一个结点，当前结点，当前结点的后一个结点

1. next指向当前结点的后一个结点即head.next，防止head.next丢失
2. 将head.next指向pre，反转。
3. 当前结点成为pre，即pre=head
4. 下一个结点成为当前结点head=next
5. 以此类推

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head==null) return null;
        ListNode pre=null;//head为当前结点，pre为head前一个结点
        ListNode next=null;//next为head后一个结点
        while(head!=null){//遍历到末尾
            next=head.next;//保存当前结点的下一个结点，避免丢失，因为当前结点要改成指向前一个结点
            head.next=pre;//当前结点指向前一个结点
            pre=head;//当前结点变为前结点
            head=next;//当前结点为下一个结点
        }
        return pre;
    }
}