6-2 reverse linked list
时间: 2023-04-27 15:00:34 浏览: 69
6-2 反转链表
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题?
相关问题
C plus plus Linked List Inversion
链表反转是一道经典的算法问题,可以使用迭代或递归两种方法来实现。以下是使用迭代方法实现 C++ 链表反转的示例代码:
```cpp
#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* prev = NULL;
ListNode* curr = head;
while (curr != NULL) {
ListNode* nextTemp = curr->next;
curr->next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
};
int main() {
ListNode* head = new ListNode(1);
head->next = new ListNode(2);
head->next->next = new ListNode(3);
head->next->next->next = new ListNode(4);
Solution solution;
ListNode* newHead = solution.reverseList(head);
while (newHead != NULL) {
cout << newHead->val << " ";
newHead = newHead->next;
}
return 0;
}
```
在这个示例代码中,我们定义了一个 `ListNode` 结构体来表示链表节点,它包含一个整数 `val` 和指向下一个节点的指针 `next`。然后我们使用迭代方法实现了 `reverseList` 函数,该函数接受一个链表头指针 `head`,并返回一个新的链表头指针,该链表是输入链表的反转。
在 `reverseList` 函数中,我们定义了两个指针 `prev` 和 `curr`,分别指向当前节点的前一个节点和当前节点。然后我们使用一个 `while` 循环遍历整个链表,每次将当前节点的 `next` 指针指向前一个节点 `prev`,然后将 `prev` 指针指向当前节点 `curr`,将 `curr` 指针指向下一个节点 `nextTemp`。最后返回 `prev` 指针,它指向了反转后的链表头节点。
在 `main` 函数中,我们创建了一个包含四个节点的链表,并将其传递给 `reverseList` 函数进行反转。最后我们遍历反转后的链表并输出结果。
1. Convert a binary search tree into a sorted circular doubly linked list 【Problem Description】 Given a binary search tree, you need to convert it into a circular doubly linked list, the elements in the linked list are sorted. For example, a binary search tree in Fig.1 is converted into a sorted circular doubly linked list in Fig.2. 【Basic Requirements】 The input data is a set of data elements to build a binary search tree, you should design algorithms to realize the conversion process and verify the accuracy of your code on multiple test data. The output includes the following: (1) Print the binary search tree (2) Traverse the binary search tree (3) Print the converted doubly linked list (4) Output all elements of the doubly linked list in positive and reverse order
【Solution】
To convert a binary search tree into a sorted circular doubly linked list, we can use the following steps:
1. Inorder traversal of the binary search tree to get the elements in sorted order.
2. Create a doubly linked list and add the elements from the inorder traversal to it.
3. Make the list circular by connecting the head and tail nodes.
4. Return the head node of the circular doubly linked list.
Here's the Python code for the solution:
```
class Node:
def __init__(self, val):
self.val = val
self.prev = None
self.next = None
def tree_to_doubly_list(root):
if not root:
return None
stack = []
cur = root
head = None
prev = None
while cur or stack:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
if not head:
head = cur
if prev:
prev.right = cur
cur.left = prev
prev = cur
cur = cur.right
head.left = prev
prev.right = head
return head
```
To verify the accuracy of the code, we can use the following test cases:
```
# Test case 1
# Input: [4,2,5,1,3]
# Output:
# Binary search tree:
# 4
# / \
# 2 5
# / \
# 1 3
# Doubly linked list: 1 <-> 2 <-> 3 <-> 4 <-> 5
# Doubly linked list in reverse order: 5 <-> 4 <-> 3 <-> 2 <-> 1
root = Node(4)
root.left = Node(2)
root.right = Node(5)
root.left.left = Node(1)
root.left.right = Node(3)
head = tree_to_doubly_list(root)
print("Binary search tree:")
print_tree(root)
print("Doubly linked list:")
print_list(head)
print("Doubly linked list in reverse order:")
print_list_reverse(head)
# Test case 2
# Input: [2,1,3]
# Output:
# Binary search tree:
# 2
# / \
# 1 3
# Doubly linked list: 1 <-> 2 <-> 3
# Doubly linked list in reverse order: 3 <-> 2 <-> 1
root = Node(2)
root.left = Node(1)
root.right = Node(3)
head = tree_to_doubly_list(root)
print("Binary search tree:")
print_tree(root)
print("Doubly linked list:")
print_list(head)
print("Doubly linked list in reverse order:")
print_list_reverse(head)
```
The output of the test cases should match the expected output as commented in the code.