如题
思路：第一反应就是交换相邻两个节点的数据域，容易实现。但应记住第二种方法：交换指针域实现交换，如果链表有偶数个节点，交换相邻节点；如果有奇数个节点，交换除最后一个节点之外的其他相邻节点。
Snip20181014_2.png
void Reverse(LinkList head)
{
if(head == NULL || head->next == NULL)
return false;
LNode* pre = head;
LNode* cur = head->next;
LNode* next = NULL;
while(cur && cur->next)
{
next = cur->next->next; // 1)
pre->next = cur->next; // 2)
cur->next->next = cur; // 3)
cur->next = next; // 4)
pre = cur;
cur = next;
}
}
需要一次遍历：T(n) = O(n) , 空间=O(1)
网友评论