设计算法,将一个非空单链表中序号从 i 到 j 的结点逆置。
时间: 2023-06-01 16:02:42 浏览: 134
1. 首先判断链表是否为空,如果为空则直接返回。
2. 将链表的第 i-1 个结点记为 prev,第 i 个结点记为 cur,第 j 个结点记为 end,第 j+1 个结点记为 next。
3. 遍历链表,找到 cur 和 end,同时记录 prev 和 next。
4. 将从 cur 到 end 的结点逆置。
5. 将 prev 的 next 指向 end,cur 的 next 指向 next。
6. 返回逆置后的链表。
算法实现:
```
public ListNode reverseBetween(ListNode head, int i, int j) {
if (head == null) {
return null;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
for (int k = 1; k < i; k++) {
prev = prev.next;
}
ListNode cur = prev.next;
ListNode end = cur;
ListNode next = cur.next;
for (int k = i; k < j; k++) {
ListNode temp = next.next;
next.next = cur;
cur = next;
next = temp;
}
prev.next = cur;
end.next = next;
return dummy.next;
}
```
阅读全文