---

1 题目描述

---

输入一个链表，反转链表后，输出链表的所有元素。

2 思路

---

1. 反转链表可以通过栈作为辅助数组，先将链表节点全部入栈，然后逐个出栈重新构造链表，但这样会占用额外的空间；
2. 不需要辅助空间的解法是直接翻转相邻节点的指针，通过三个指针分别指向前一节点、当前节点、下一节点，但这会改变原有链表的结构。
3. 因此，采用何种思路应考虑具体要求。

3 代码实现

---

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head==null){
            return null;
        }
        ListNode p = head;
        ListNode q = p.next;
        ListNode r = null;
        head.next = null;
        
        while(q!=null){
            r = q.next;
            q.next = p;
            p = q;
            q = r;
        }

        return p;
    }
}

comments powered by Disqus