欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

剑指offer学习笔记——链表2:单链表的翻转(非递归&递归)

程序员文章站 2024-03-06 20:46:14
...

对应于剑指offer代码鲁棒性面试题16——反转链表:

题目:输入一个链表,反转链表后,输出反转之后链表的头结点。

求解思路:

有非递归与递归两种解法:

1、如果用非递归,为了防止反转一个结点之后链表断掉,我们必须记录当前结点cur,当前结点之前的节点pre,以及当前结点之后的节点post。

2、如果使用递归,我们就假设当前结点之后的都已经反转好了。仅仅需要将当前结点之后的结点(post)连到当前结点,当前结点指向NULL即可。

注意!!!为保证鲁棒性,最好事先想好特殊测试样例:

1)输入的链表表头为NULL

2)输入的链表只有一个结点

3)输入的链表有多个结点

具体代码如下:

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/

class Solution {
public:
    //方法一:非递归的思路
    ListNode* ReverseList(ListNode* pHead) {
        if(pHead==NULL)
           return NULL;
        ListNode *pre = NULL,*cur = pHead,*post = NULL;
        while(cur!=NULL)
        {
            post = cur->next;
            cur->next = pre;
            pre = cur;
            cur = post;
        }
        return pre;
    }
    
    
    //方法二:递归思路
    ListNode* ReverseList(ListNode* pHead) {
        if(pHead==NULL)
            return NULL;
        return RecursionReverse(pHead);
        
    }
    ListNode* RecursionReverse(ListNode* pNode)
    {
        if(pNode->next==NULL)
            return pNode;
        ListNode* pHead = RecursionReverse(pNode->next);
        pNode->next->next = pNode;
        pNode->next = NULL;
        return pHead;
    }
};

相关标签: 链表 翻转