反转链表
方法1 调转链表法
设置三个指针:
cur:用于保存当前节点的位置
pre:用于保存前一个节点位置,方便移动
nex:用于保存原本下一个节点的位置,防止丢失节点信息
利用循环每一次都将cur和pre前移,再将cur下一个节点由nex调转至pre。具体步骤如下:
nex = cur.next;
cur.next = pre;
pre = cur; cur = nex;
public class Solution { public ListNode ReverseList(ListNode head) { ListNode nex = null; ListNode cur = head; ListNode pre = null; while(cur != null){ nex = cur.next; cur.next = pre; pre = cur; cur = nex; } return pre; } }
方法2 栈解决法
这道题我首先想到的是用栈解决,将链表装进栈中,然后再从栈中弹出构建新的链表
但在这里似乎不能使用栈Stack类。