我要评论题目描述
输入一个链表，反转链表后，输出新链表的表头。
解法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
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请 点击进行留言回复，万千网友为您解惑！
网友评论