设计算法,实现单链表的逆置。即1-》2-》3-》4+++变成4-》3-》2-》1
时间: 2024-10-21 13:11:03 浏览: 14
单链表的逆置可以通过破坏性逆置和构造性逆置两种方式实现。
破坏性逆置:遍历单链表,将每个节点的next指针指向其前一个节点,最后将头节点的next指针置为NULL。这种方法会破坏原有的单链表结构,但是实现简单,时间复杂度为O(n)。
构造性逆置:遍历单链表,将每个节点的值存入一个数组中,然后再从数组中构造一个新的单链表。这种方法不会破坏原有的单链表结构,但是需要额外的空间存储数组,时间复杂度为O(n)。
下面是两种方法的具体实现:
破坏性逆置:
```
void reverseList(ListNode* head) {
ListNode* prev = NULL;
ListNode* curr = head;
while (curr != NULL) {
ListNode* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
head = prev;
}
```
构造性逆置:
```
ListNode* reverseList(ListNode* head) {
vector<int> vals;
ListNode* curr = head;
while (curr != NULL) {
vals.push_back(curr->val);
curr = curr->next;
}
ListNode* newHead = new ListNode(0);
ListNode* prev = newHead;
for (int i = vals.size() - 1; i >= 0; i--) {
ListNode* newNode = new ListNode(vals[i]);
prev->next = newNode;
prev = newNode;
}
return newHead->next;
}
```
阅读全文