LeetCode反转链表的方式有哪些
1. 迭代法
迭代法是一种常见且简洁的解法。具体操作如下:
1)定义三个指针:pre指向前一个节点,cur指向当前节点,next指向下一个节点。
2)在迭代过程中,改变节点之间的指向关系,使当前节点指向前一个节点。
3)根据条件判断是否继续迭代,直至链表尾节点为null。
// 迭代法
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
2. 递归法
递归法是将问题拆解成子问题来解决,解决子问题后再逐步返回结果。
具体步骤如下:
1)递归到链表的末尾节点,将其作为新的头节点返回。
2)递归返回时,将当前节点的下一个节点指向当前节点。
3)通过递归的方式不断改变指向关系,完成链表的反转。
// 递归法
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode p = reverseList(head.next);
head.next.next = head;
head.next = null;
return p;
}
3. 头插法
头插法是一种常用的反转链表的方法,也是迭代法的一种变形。
具体步骤如下:
1)定义一个新的空节点dummy,作为新链表的头节点。
2)迭代遍历原链表的所有节点,将每个节点插入到dummy节点之后,从而实现链表反转。
3)返回dummy节点的下一个节点,即为反转后的链表头节点。
// 头插法
public ListNode reverseList(ListNode head) {
ListNode dummy = new ListNode(-1);
while (head != null) {
ListNode temp = head.next;
head.next = dummy.next;
dummy.next = head;
head = temp;
}
return dummy.next;
}
以上是三种常用的反转链表的方法,迭代法、递归法和头插法。每种方法各有特点,可以根据实际情况选择适合的方法来解决问题。
本文由轻山版权所有,禁止未经同意的情况下转发
上一篇
怎么为CDSW的数据目录扩容 猜您想看
-
你一定没发现,这个网易云音乐小功能竟然如此好用!
网易云音乐小功...
2023年05月15日 -
如何使用iPhone上的多点触控和滚动技巧提高工作效率
如何使用iPh...
2023年05月05日 -
elasticsearch的使用示例分析
一、概述Ela...
2023年07月22日 -
宝塔如何让你的git仓库连接到其他服务器以实现仓库之间的数据传递
随着现代社会的...
2023年05月12日 -
C++常见的内存泄漏有哪些
未及时释放动态...
2023年07月21日 -
Kafka的生产者优秀架构设计的示例分析
Kafka生产...
2023年05月22日