我想知道是否存在某种逻辑,可以只用两个指针来反转一个单链表.
以下内容用于使用三个指针(即p
、q
、r
)反转单链表:
struct node {
int data;
struct node *link;
};
void reverse() {
struct node *p = first,
*q = NULL,
*r;
while (p != NULL) {
r = q;
q = p;
p = p->link;
q->link = r;
}
first = q;
}
是否有其他替代方案可以反转链表?就时间复杂性而言,反转单链表的最佳逻辑是什么?