用时间复杂度为n的算法,将一个长度为n的单链表逆序排列
时间: 2024-03-22 17:37:21 浏览: 31
可以使用迭代的方式对单链表进行逆序排列。具体步骤如下:
1. 定义三个指针,分别指向当前节点、前一个节点和后一个节点。
2. 将当前节点的 next 指针指向前一个节点。
3. 将前一个节点指针后移,指向当前节点。
4. 将当前节点指针后移,指向后一个节点。
5. 重复步骤2到4,直到当前节点为 null,表示已经遍历完整个链表。
6. 将链表的头节点指向前一个节点。
代码实现如下:
```java
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
```
时间复杂度为 O(n),空间复杂度为 O(1)。
相关问题
用时间复杂度为n的算法,将一个长度为n的单链表逆序排列。
可以使用迭代法或递归法来实现单链表的逆序排列。
迭代法的实现思路是,依次将每个节点的 next 指针指向它的前驱节点。具体步骤如下:
1. 定义三个指针 prev、curr 和 next,分别指向当前节点的前驱节点、当前节点和当前节点的后继节点。
2. 遍历单链表,对于当前节点,将它的 next 指针指向它的前驱节点 prev,然后将 prev、curr 和 next 指针同时向右移动一个节点。
3. 当遍历到最后一个节点时,将它的 next 指针指向它的前驱节点 prev,并将它设为新的头节点。
代码如下:
```python
def reverseList(head):
if not head or not head.next:
return head
prev, curr, next = None, head, head.next
while curr:
curr.next = prev
prev = curr
curr = next
next = next.next if next else None
return prev
```
递归法的实现思路是,先递归地反转后续节点,然后将当前节点的 next 指针指向它的后继节点的后继节点。具体步骤如下:
1. 递归地反转当前节点后面的节点。
2. 将当前节点的 next 指针指向它的后继节点的后继节点。
3. 返回新的头节点。
代码如下:
```python
def reverseList(head):
if not head or not head.next:
return head
newHead = reverseList(head.next)
head.next.next = head
head.next = None
return newHead
```
这两种方法的时间复杂度均为 O(n),空间复杂度为 O(1)。
将长度为n的单链表连接在长度为m的单链表之后的算法的时间复杂度为?
将长度为n的单链表连接在长度为m的单链表之后的算法时间复杂度为O(n),其中n为第一个链表的长度。具体实现步骤如下:
1. 找到第一个链表的尾结点,需要遍历整个链表,时间复杂度为O(n);
2. 将第一个链表的尾结点的next指针指向第二个链表的头结点,时间复杂度为O(1);
3. 整个连接操作完成,时间复杂度为O(n)。
因此,将长度为n的单链表连接在长度为m的单链表之后的算法的时间复杂度为O(n)。