反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题?
public ListNode reverseList(ListNode head) { ListNode pre = null; //头结点变尾节点,指向null while(head!=null){ ListNode next = head.next; head.next = pre; pre = head; head = next; } return pre; } public ListNode reverseList2(ListNode head) { //递归 return reverseListInt(head, null); } private ListNode reverseListInt(ListNode head, ListNode pre) { if (head == null) return pre; ListNode next = head.next; head.next = pre; return reverseListInt(next, head); //尾递归,操作已经完成,最后返回最后结果罢了 } }
栈实现
class Solution { public ListNode reverseList(ListNode head) { ListNode resListNode = new ListNode(0) ; ListNode pListNode = head; ListNode res = resListNode; Stack<Integer> st = new Stack<Integer>(); while(pListNode!=null) { st.push(pListNode.val); pListNode = pListNode.next; } while(!st.empty()) { res.next = new ListNode(st.peek()); st.pop(); res = res.next; } return resListNode.next; } }