题目描述
输入一个链表,反转链表后,输出新链表的表头。
解法1
可以使用三个辅助指针pHead, last,next
pHead记录当前节点,last记录上一个节点,next记录下一个节点
首先使用next保存当前节点的下一个节点,然后将当前节点的下一个节点指向last,实现反转
如下图所示
实现代码
public ListNode ReverseList(ListNode pHead)
{
ListNode last = null, next = null;
while(pHead != null){
next = pHead.next;
pHead.next = last;
last = pHead;
pHead = next;
}
return last;
}
解法2
解法1是将链表按照从头到尾的顺序反转的
可以使用递归,通过不断递归深入,实现先从链表的尾节点开始反转
然后通过递归的回溯实现按照从尾到头的顺序反转每个节点
如下图所示
实现代码
public ListNode ReverseList2(ListNode pHead)
{
if(pHead == null || pHead.next == null) return pHead;
ListNode node = ReverseList2(pHead.next);
pHead.next.next = pHead;
pHead.next = null;
return node;
}
更多算法题目的完整描述,AC代码,以及解题思路可以查看GitHub仓库Algorithm