反转链表

问题陈述

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

思路分析

先将结点一个个存入栈，然后逐次弹栈取出。

代码实现

public class Reverse_LinkList {
    public ListNode reverseLinklist(ListNode head){
        if(head==null||head.next==null) return head;  //判断链表是否为空，非常重要。
        Stack<ListNode> stack=new Stack();         //定义一个ListNode类型的栈
        ListNode first=head;         //定义一个初始化结点等于head
        while(first!=null){
            stack.push(first);
            first=first.next;
        }
        head=stack.pop();  //定义头结点为第一个弹栈元素
        first=head;          //定义初始化结点等于此处的head
        while (!stack.isEmpty()){
            first.next=stack.pop();
            first=first.next;
        }
        first.next=null; //弹栈完成，置next为空。
        return head;

    }
    public static void main(String[] args){
        ListNode head=new ListNode(4);
        head.next=new ListNode(3);
        head.next.next=new ListNode(9);
        Reverse_LinkList reverse_linkList=new Reverse_LinkList();
        System.out.println(reverse_linkList.reverseLinklist(head).val);
    }
}

双指针迭代

class Solution{
    public ListNode reverselist(ListNode head){
        if(head==null||head.next==null) return head;
        ListNode pre=null;
        ListNode cur=head;
        while(cur!=null){
            ListNode temp=cur.next;//暂存当前结点的next
            cur.next=pre;//将当前结点的next指向pre
            cur=temp;//cur往后
            pre=cur;//pre往后
        }
        return pre;//当cur为空跳出循环，pre正好指向末尾元素，且实现了指向反转。
    }
}