单链表原地逆置
给定一个带头结点的单链表,编写算法将其原地逆置。所谓“原地”是指空间复杂度为
O(1)。有两种方法,头插法和冒泡法。这两种方法的时间复杂度均为 O(n)。
头插法
思路
我们知道,用头插法建立链表,得到的链表中元素的顺序和输入的顺序相反,所以利用这
一特点,可以将链表逆置。
给定一个带头结点的单链表 L,如下图所示。
首先用指针 p 存储链表第一个结点,然后将头结点从链表中剥离下来,如下图所示,此时
链表 L 只有一个头结点。
另设一指针 r 保存 p 的后继,将 p 指向的结点 N1 用尾插法插入到链表 L 中,
此时 p 指向 N2,保存 p 的后继 N3,再将 N2 尾插到链表 L 中,