设有一个表头指针为HEAD的单链表。试设计一个算法,通过遍历一趟链表,将链表中所有节点的链接方向逆转。要求逆转结果中链表的表头指针 HEAD指向原链表的最后一个节点。
时间: 2024-10-01 22:06:11 浏览: 50
链表_链表_用链表将两个数组升序合并到另一个数组_
要实现这个操作,可以采用迭代的方式。以下是步骤:
1. **初始化两个指针**:创建两个指针`prev`和`current`,分别初始化为`NULL`和`HEAD`。
- `prev`用于保存当前节点的前驱节点,初始时没有前驱。
- `current`用于遍历链表。
2. **遍历链表**:当`current`不为`NULL`时,进入循环。
- 记录当前节点的下一个节点:`nextNode = current->next`。
- 更新当前节点的指向下一位:`current->next = prev`。
- 移动指针到下一个节点:`prev = current`。
- `current`向前移动:`current = nextNode`。
3. **处理特殊情况**:在遍历结束时,即`current`变为`NULL`,将`prev`设置为新的头结点,因为经过上面的操作,`prev`已经指向了原链表的最后一个节点。
4. **返回新表头**:最后返回`prev`作为逆转后的链表的新头结点。
算法伪代码如下:
```plaintext
function reverseList(HEAD):
prev = NULL
current = HEAD
while current is not NULL:
nextNode = current.next
current.next = prev
prev = current
current = nextNode
HEAD = prev # 新的头结点是原来的尾结点
return HEAD
```
阅读全文