给定一个单链表的头结点head(该头节点是有值的,比如在下图,它的val是1),长度为n,反转该链表后,返回新链表的表头。
数据范围: 0\leq n\leq10000≤n≤1000
要求:空间复杂度 O(1)O(1) ,时间复杂度 O(n)O(n) 。
如当输入链表{1,2,3}时,
经反转后,原链表变为{3,2,1},所以对应的输出为{3,2,1}。
以上转换过程如下图所示:
解法一:迭代法
遍历链表,使当前指针cur指向它的前一个节点,但此时由于cur指针指向前一个节点,会丢失cur节点的下一个节点的信息,必须先对当前指针cur的下一个节点信息作为记录,当遍历结束后,我们返回当前指针cur的上一个节点,此时cur节点的上一个节点刚好是我们需要返回新链表的表头。
//迭代方式
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* cur = head;//当前节点
ListNode* prev = NULL;//上一个节点
ListNode* tmp = NULL;//当前节点指向上一个节点的时候,记录当前节点的下一个节点
while(cur!=NULL)
{
tmp=cur->next;
cur->next=prev;
prev = cur;
cur=tmp;
}
return prev;//此时当前节点指向最后一个节点的下一个节点
//即当前节点为空,prev节点是我们需要返回的新节点
}
};
解法二:递归法
当我们达到递归所能划分的最小子问题时,再次递归已经没有意义,此时我们归,反转函数。使用递归函数,一直递归到链表的最后一个结点,该结点就是反转后的头结点,记作 p
此后,函数返回时,让当前指针的下一个节点的next域指向head,同时将head的next域置为NULL
从而实现从链表尾部开始的局部反转,当递归函数全部出栈后,链表反转完成。
//递归实现
class Solution {
public:
ListNode* reverseList(ListNode* head) {
//递归终止条件 剩下一个节点的时候返回head
if( head==NULL || head->next==NULL)
{
return head;
}
ListNode* p = reverseList(head->next); //当最p指向最后一个节点
//递归归的过程
head->next->next = head;
head->next = NULL;
return p;
}
};
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)