牛客-面试必刷-BM1反转链表

反转链表

思路1

利用栈的特性先进后出直接反转，并且此处反转的只有节点值不需要把每个节点都反转。

public ListNode ReverseList (ListNode head){
        Stack<Integer> stack = new Stack<>();
        ListNode temp = head;
        while(temp != null){
            stack.push(temp.val);
            temp = temp.next;
        }
        temp = head;
        while(temp != null){
            temp.val = stack.pop();
            temp = temp.next;
        }
        return head;
    }

思路2

遍历节点的同时逆转链表，即让当前节点指向下一个节点的指针指向前一个节点，在此过程中要保存下一节点的信息，需要用到辅助节点

public ListNode ReverseList (ListNode head) {
		//last保存下一节点，front作为前一节点
        ListNode front = null;
        ListNode last = null;

        while(head != null) {
        	//从第一个开始逆转，先保存下一个节点的信息，让第一个节点的下一个节点变为null
            last = head.next;
            head.next = front;
            //然后把辅助节点后移，此时head也变成辅助节点，然后回到循环开始，last又开始存储head下一个节点
            front = head;
            head = last;
        }
        return front;
    }