AcWing 35. 反转链表完整注释
原题链接
简单
作者:
畅想心繁
,
2021-05-08 12:47:10
,
所有人可见
,
阅读 336
import java.util.Stack;
public class AC35 {//反转链表
static class ListNode{
int val;
ListNode next;
ListNode(int x){val=x;}
}
public static void main(String[] args) {
ListNode a=new ListNode(0);
ListNode b=new ListNode(1);
ListNode c=new ListNode(2);//测试
a.next=b;
b.next=c;
System.out.println(reverse(a).val);
}
private static ListNode reverse(ListNode head){
if(head==null)return head;
ListNode dummy=new ListNode(0);
dummy.next=head;
ListNode cur=head.next;//插入dummy后的节点
ListNode tail=head;//tail作为头节点不变
while(cur!=null){
ListNode n=cur.next;//存连之前的next,为下一次更新做准备
cur.next=dummy.next;//next变化连到变化后的指针
dummy.next=cur;//更新仿造指针的next
tail.next=n;//将已经反转的部分链表和剩余还需要反转的链表相连
cur=n;//下一节点
}
return dummy.next;//迭代
}
private static ListNode reverseList(ListNode head){
if(head==null||head.next==null)return head;
ListNode tail=reverseList(head.next);
head.next.next=head;//我连我自己
head.next=null;//更新当前自己的next
return tail;//递归
}
private static ListNode reverseList2(ListNode head) {//用栈实现
if(head == null){
return head;
}
Stack<ListNode> stack = new Stack();
ListNode cur = head;
while(cur != null){
stack.push(new ListNode(cur.val));
cur = cur.next;
}
cur = stack.pop();
ListNode newHead = cur;
while (!stack.isEmpty()) {
cur.next = stack.pop();
cur = cur.next;
}
return newHead;
}
}