4-13 DSA 关于单链表逆置总结

单链表的逆置算法 包括 复制逆置 递归逆置 就地逆置
复制逆置 递归逆置 => T(n) = O(n) | S(n) = O(n)
就地逆置 => T(n) = O(n) | S(n) = O(1)

##

复制逆置

思路:将原链表结点 头插到新链表中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 单链表结点复制逆置 S(n) = O(n)
pointer reverseListByCopy(lklist L)
{
// 初始化newList
lklist newList;
pointer p;
newList = new node; // 非常重要的一步!!!
newList->data = L->data;
newList->next = NULL;
// 复制逆置
while(L->next != NULL){
p = newList->next;
newList->next = L->next;
L->next = L->next->next;
newList->next->next = p;
}
destoryList(L); // 销毁原来的单链表 函数方法自己填写
return newList;
}

就地逆置

思路:(普通循环)在原结点上修改 辅助结点空间为O(1) 「头插法实现」
图解:
WechatIMG1.jpeg

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 单链表结点就地逆置 S(n) = O(1)
// 即在原结点上修改 辅助结点空间为O(1) 头插法实现
void reverseListByHead(lklist L)
{
pointer p, r;
p = L->next; //将头结点指向p结点
L->next = NULL;
while (p != NULL)
{
r = p->next;
p->next = L->next;
L->next = p;
p = r;
}
delete p; // 删除辅助结点
delete r;
}

## 递归逆置 思路:直接扫描链表 将各结点的next指针改为其前趋 「递归实现」
1
2
3
4
5
6
7
8
9
10
11
12
// 单链表结点递归逆置 S(n) = O(n)
// 直接扫描链表 将各结点的next指针改为其前趋 辅助结点空间为O(n)
void reverseListByRecursion(lklist &L)
{
pointer p;
if (L == NULL || L->next == NULL) return;
p = L->next;
reverseListByRecursion(p);
L->next->next = L;
L->next = NULL;
L = p;
}

最后

代码可在我的github上获取哦
https://github.com/leekachung/Daily-DSA/blob/master/List/linkedlist/singly.cpp

# DSA

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×