链接
https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/
难度: #简单
题目
定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
限制:
0 <= 节点个数 <= 5000
注意:本题与主站 206 题相同:https://leetcode-cn.com/problems/reverse-linked-list/
代码框架
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
}
}
题目解析
解答思路1:
递归解法,
不断递归找到链表的最后一个非空结点,
然后返回该结点作为反转后的链表结点,
然后递归回到上一个结点,
把当前结点的后一个结点反转,
即将后一个结点指向当前结点,
当前结点指向null,
不断回退到上一个结点,
不断反转链表到头结点即可。
画图演示思路:
解答思路2:
使用While循环从前往后反转链表结点,
使用三个结点指针,
保存前一个pre,当前cur,下一个next三个结点
先保存当前节点的下一个节点next=cur.next;
然后把当前节点指向前一个节点:cur.next=pre;
最后pre和cur都向后移动一个节点,
pre=cur;
cur=next。
直到当前节点cur为null,
则pre为新的链表的头结点。
画图演示思路:
测试用例
package edu.yuwen.sowrd.num24.solution;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;
import edu.yuwen.sowrd.entity.ListNode;
import edu.yuwen.sowrd.num24.sol2.Solution;
public class SolutionTest {
/**
* 输入: 1->2->3->4->5->NULL
* 输出: 5->4->3->2->1->NULL
*/
@Test
public void testCase1() {
Solution solution = new Solution();
ListNode node1 = new ListNode(1);
ListNode node2 = new ListNode(2);
ListNode node3 = new ListNode(3);
ListNode node4 = new ListNode(4);
ListNode node5 = new ListNode(5);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
ListNode head = node1;
ListNode newHead = solution.reverseList(head);
for (int i = 5; i <= 1; i--) {
Assertions.assertEquals(i, newHead.val);
newHead = newHead.next;
}
}
/**
* 输入: NULL
* 输出: NULL
*/
@Test
public void testCase2() {
Solution solution = new Solution();
ListNode head = null;
ListNode newHead = solution.reverseList(head);
Assertions.assertNull(newHead);
}
}
解答1
package edu.yuwen.sowrd.num24.sol1;
import edu.yuwen.sowrd.entity.ListNode;
public class Solution {
public ListNode reverseList(ListNode head) {
// 如果链表头部为空则返回null
// 否则遍历到链表结尾,返回最后一个节点
if (head == null || head.next == null) {
return head;
}
// 递归遍历下一个结点
ListNode curHead = reverseList(head.next);
// 当前结点的后一个结点
ListNode nextNode = head.next;
// 反转,将后一个结点指向当前结点
nextNode.next = head;
// 当前结点指向null
head.next = null;
// 返回递归遍历到的最后一个节点
return curHead;
}
}
解答2 推荐
package edu.yuwen.sowrd.num24.sol2;
import edu.yuwen.sowrd.entity.ListNode;
public class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// 使用三个指针保存前一个,当前,下一个这三个结点
ListNode pre = null;
ListNode cur = head;
ListNode next = null;
// 当前结点为空就是到了链表尾部
while (cur != null) {
// 先保存cur的next结点
next = cur.next;
// 反转链表,当前结点指向上一个结点
cur.next = pre;
// 两个指针同时向后移动一个结点
pre = cur;
cur = next;
}
// 这时候cur指向null,pre才是反转后的链表头
return pre;
}
}
网友评论