新建虚拟头,遍历原链表解法
一个比较简单可以将所有操作融合的解法是先新建一个虚拟头,然后依次遍历原链表,每次将正在遍历的位置插入到头结点,这样遍历完成后,得到的就是反转后的链表。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode dummy = new ListNode(-1);
ListNode p = head;
while(p != null) {
ListNode temp = new ListNode(p.val);
temp.next = dummy.next;
dummy.next = temp;
p = p.next;
}
return dummy.next;
}
}
栈解法
也可以借助栈来实现,先将所有节点添加进栈中,再依次出栈也可以得到反转后的新链表。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
Stack<ListNode> st = new Stack<>();
ListNode p = head;
while(p != null) {
st.push(p);
p = p.next;
}
ListNode dummy = new ListNode(-1);
ListNode tail = dummy;
while(!st.isEmpty()) {
tail.next = st.pop();
tail = tail.next;
tail.next = null;
}
return dummy.next;
}
}
递归解法
递归解法实际底层调用了系统的栈,我们要明确由于是需要反转链表,所以是在出栈是将节点添加到新链表上,这样才能保证最后的节点在最前面,达到反转的效果。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode dummy = new ListNode(-1);
dfs(head, dummy);
return dummy.next;
}
private void dfs(ListNode head, ListNode newHead) {
if(head == null) return ;
ListNode newNode = new ListNode(head.val);
newNode.next = newHead.next;
newHead.next = newNode;
dfs(head.next, newHead);
}
}