【数据结构】--单链表力扣面试题②反转链表-Toy模板网

这篇具有很好参考价值的文章主要介绍了【数据结构】--单链表力扣面试题②反转链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目链接：反转链表

法一：直接反转法

法二：头插法

题目链接：反转链表

【数据结构】--单链表力扣面试题②反转链表

题目分析：

创建一个新链表，然后值是逆置的行吗？不行。因为题目要求的是在原链表上逆置，改变原链表的指向，并不是值的拷贝后的逆转。那其实总共有三种方法。法一，直接原地翻转。法二，头插法。法三，递归法。这里讲解法一法二。因为能用循环就用循环，没必要用递归，因为递归有缺陷，如果链表够长的话，肯定会造成栈溢出，栈的空间本来就不大。

法一：直接反转法

解题思路：

定义两个变量指针指向节点

如图，我们可以让n2的next指针域指向n1,然后让n2指向现节点的下一节点，但是怎么找下一节点？遇到这种情况我们就可以再创建一个指针n3，这样就能找到下一节点了，因为这个过程需要遍历链表，所以需要n3

n1和n2是用来翻转链表的，n3是用来迭代

迭代到最后

终止条件：n2==NULL，而不是第一次n3==NULL，因为若此时终止，n2的节点的指针域还未指向n1，最终可知新头结点是n1

C++版本代码：

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr) return nullptr;

        ListNode* n1 = nullptr, *n2 = head, *n3 = head->next;
        while (n2)
        {
            n2->next = n1;
            n1 = n2;
            n2 = n3;
            if (n3) n3 = n3->next;
        }
        return n1;
    }
};

C版本代码：

struct ListNode* reverseList(struct ListNode* head)
{
	if (!head)//如果为空 !NULL为真，则返回NULL
	{
		return NULL;
		//如果为空链表，则无需翻转，直接返回NULL，
		//如果此刻你不返回，那么会对NULL指针解引用，会非法访问内存
	}

	struct ListNode* n1, * n2, * n3;
	n1 = NULL;
	n2 = head;
	n3 = head->next;

	while (n2)//通过画图可知，n2为空时就是翻转完毕的时候
	{
		n2->next = n1;//翻转链表

		n1 = n2;//迭代
		n2 = n3;//迭代
		if (n3)//如果n3已经为NULL了，就没有必要走这个循环了
			n3 = n3->next;
	}

	return n1;
}

法二：头插法

解题思路：取原链表中的节点，头插到新链表newhead中。

【数据结构】--单链表力扣面试题②反转链表

C++版本代码：

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* cur = head, *next = nullptr, *newhead = nullptr;
        while (cur)
        {
            next = cur->next;
            //头插
            cur->next = newhead;
            newhead = cur;
            cur = next;
        }
        return newhead;
    }
};

C版本代码：文章来源地址https://www.toymoban.com/news/detail-457540.html

struct ListNode* reverseList(struct ListNode* head)
{//这种情况不用格外考虑是不是空链表的问题，因为如果是，循环都进不去，直接返回NULL
	struct ListNode* cur = head;
	struct ListNode* next = NULL;
	struct ListNode* newhead = NULL;
	while (cur)
	{
		next = cur->next;
		//头插
		cur->next = newhead;
		newhead = cur;
		//迭代往后走
		cur = next;
	}
	return newhead;
}

到了这里，关于【数据结构】--单链表力扣面试题②反转链表的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！