剑指offer-15-反转链表

思路

• 三指针
• 临时保存链表

代码

三指针

import java.util.*;
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head==null || head.next==null){return head;}
        ListNode nex=head.next,cur=head,pre=null;
        while(nex!=null){
            cur.next=pre;
            pre=cur;
            cur=nex;
            nex=nex.next;
        }
        cur.next=pre;
        return cur;
    }
}

临时保存链表（栈）

import java.util.*;
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head==null || head.next==null){return head;}
        Stack<ListNode> stack=new Stack();
        while(head!=null){
            stack.push(head);
            head=head.next;
        }
        ListNode h= stack.peek();
        ListNode p=h;
        while(!stack.isEmpty()){
            ListNode temp=stack.pop();
            p.next=temp;
            p=p.next;
        }
        p.next=null;
        return h;
    }
}