剑指Offer(15)--反转链表
程序员文章站
2022-03-14 21:18:10
...
题目描述
输入一个链表,反转链表后,输出新链表的表头。
思路与解答
首先,使用循环解答,不断把指向下一个的指针,指向前面的。假设链表是1->2->3->4,那么执行一次循环里面的内容的图示如下:
直到head==null的时候,返回first即可。
public static ListNode ReverseList(ListNode head) {
if (head == null) {
return head;
} else {
ListNode first = null;
while (head!= null) {
ListNode temp = head.next;
head.next = first;
first = head;
head = temp;
}
return first;
}
}
还有一种方法,是头插法,也就是先初始化一个listNode,初始化为0->null;然后遍历链表,不断将元素插入到0的后面。假设链表是1->2->3->4.
0->1->null
0->2->1->null
0->3->2->1->null
0->4->3->2->1->null
然后取出listnode.next即可。
public ListNode ReverseList(ListNode head) {
ListNode listnode = new ListNode(1);
while (head != null) {
ListNode next = head.next;
head.next = listnode.next;
listnode.next = head;
head = next;
}
return listnode.next;
}
推荐阅读
-
剑指Offer 34. 二叉树中和为某一值的路径(Medium)
-
剑指offer59:按之字形顺序打印二叉树:[[1], [3,2], [4,5,6,7]]
-
剑指offer64:滑动窗口的最大值
-
(难,未完)通配符或正则表达式:判断是否能匹配 == 剑指 Offer 19. 正则表达式匹配
-
《剑指offer》算法题整理
-
剑指offer11:输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。(进制转换,补码反码)
-
剑指offer第二天
-
【数组】剑指 Offer 53 - I. 在排序数组中查找数字 I(简单)
-
剑指offer面试题53:在排序数组中查找数字(Java 实现)
-
《剑指offer》面试题53:在排序数组中查找数字