剑指 Offer 24. 反转链表

转载自Leet Code《剑指Offer》

题目描述

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

示例：

输入：1->2->3->4->5->NULL 输出：5->4->3->2->1->NULL

提示：

• 0 <= 链表长度 <= 5000

---

我的思路

由于链表只能从头到尾遍历的特性，利用栈来实现对其的反转。题目描述

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

示例：

输入：1->2->3->4->5->NULL 输出：5->4->3->2->1->NULL

提示：

• 0 <= 链表长度 <= 5000

---

我的思路

由于链表只能从头到尾遍历的特性，利用栈来实现对其的反转。

---

我的代码

{.line-numbers}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class MySolutionOffer24 {
    public ListNode reverseList(ListNode head) {
    	if (head==null) return null;
    	
    	Stack<ListNode> stack = new Stack();
    	ListNode newHead = null;
    	ListNode p = head;
    	
    	while (p!=null)
    	{
    		stack.push(p); 
            p = p.next;
    	}
    	
    	ListNode pre = newHead;
        
    	while (!stack.isEmpty())
    	{
    		p = stack.pop();
            
    		if (newHead==null)
    		{
    			newHead = p; 
                pre = newHead;
    		}
    		else
    		{
    			pre.next = p;
    			pre = p;
    		}
    	}
        p.next = null;
        
    	return newHead;
    }
}