题目描述
反转单链表,并且要求原地置逆即空间复杂度为O(1)
样例
输入:1->2->3->4->5->NULL
输出:5->4->3->2->1->NULL
思路1:
将头结点摘下来,然后从第一个结点开始,依次插入到头结点的后面(头插法建立),直到最后一个为止。
C语言(实现一)
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode* Node;
struct ListNode* reverseList(struct ListNode* head) {
if(!head) return NULL;
Node tempHead = (Node)malloc(sizeof(struct ListNode));//创建一个虚拟头结点
tempHead->next = head;
Node p,r;//p为工作指针,r为p的后继,防止断链
p = tempHead->next;//让工作指针首先指向头结点的下一个结点
tempHead->next = NULL;//先将头结点单独拎出来
while(p){//采用头插法
r = p->next;//暂存p的后继,防止断链
p->next = tempHead->next;
tempHead->next = p;
p = r;
}
return tempHead->next;
}
思路2:
不好描述,需要画图,但是我不方便画图,所以直接写代码,读者可以自行根据代码画图
C语言(实现二)
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode* Node;
struct ListNode* reverseList(struct ListNode* head) {
if(!head) return NULL;
Node tempHead = (Node)malloc(sizeof(struct ListNode));//创建一个虚拟头结点
tempHead->next = head;
Node pre,p=tempHead->next,r=p->next;//三个指针相邻
p->next = NULL;//处理第一个节点
while(r){//若r为空,则说明p为最后一个节点
pre = p;
p = r;
r = r->next;
p->next = pre;//指针反转
}
tempHead->next = p;//处理最后一个节点
return tempHead->next;
}