算法日志-链表翻转

重温力扣通例算法，记载算法的演变，本日先容的是链表翻转
场景：

现在有一条单项链表，链表节点存在一个数据和指向下一个节点的指针， 怎样将其翻转过来？

输入 100->200->300->400->500
输出 500->400->300->300->100
针对该场景，我们有多种办理方式，这里我们先容最常见的两种
解法一：迭代

从前今后遍历链表，处置处罚当前节点时，必要将用额外的变量生存当前节点指向前后的节点指针，从而可以方便改变指针指向的详细信息，然后不绝地重复该过程。下面我们来详细操纵
步调

1、界说链表节点结构ListNode，包罗两个变量val和next
2、我们必要界说两个变量，变量的范例为ListNode，分别存储当前节点前后地指针信息，分别为prev和next，传入头节点

3、将头节点赋值为curr，开始循环处置处罚，将下一个节点指针生存到next变量 next=curr.next

4、将节点指针指向前一个节点prev，curr.next=prev

5、预备处置处罚下一个节点，将curr赋值给prev

6、将下一个节点赋值为curr，接着处置处罚下一个节点

1. public static ListNode reserse(ListNode head) {
2.      ListNode prev = null;
3.      ListNode next;
4.      ListNode curr = head;
5.      while (curr != null){
6.               //将当前节点未改变前 指向下一节点的信息 保存到next变量
7.          next = curr.next;
8.          //改变当前节点的指针指向， 将节点指针指向前一个节点prev
9.          curr.next = prev;
10.          //节点改变完了，然后把自己变成前一个节点，则将当前节点信息保存到prev变量
11.          prev = curr;
12.          //接着将下一节点赋予当前节点，准备处理下一节点
13.          curr = next;
14.      }
15.      //返回头节点
16.      return prev;
17. }

复制代码

完备代码

下列是完备代码，包罗测试代码

1. package com.cys.algorithm;
3. public class ReverseList {
5.     static class ListNode {
6.         int val;
7.         ListNode next;
9.         public ListNode(int val, ListNode next) {
10.             this.val = val;
11.             this.next = next;
12.         }
13.     }
15.     public static ListNode reserse(ListNode head) {
16.         ListNode prev = null;
17.         ListNode next;
18.         ListNode curr = head;
19.         while (curr != null){
20.              //将当前节点未改变前 指向下一节点的信息 保存到next变量
21.                  next = curr.next;
22.                  //改变当前节点的指针指向， 将节点指针指向前一个节点prev
23.                  curr.next = prev;
24.                  //节点改变完了，然后把自己变成前一个节点，则将当前节点信息保存到prev变量
25.                  prev = curr;
26.                  //接着将下一节点赋予当前节点，准备处理下一节点
27.                  curr = next;
28.         }
29.         return prev;
30.     }
32.     public static void main(String[] args) {
33.         ListNode node5 = new ListNode(500, null);
34.         ListNode node4 = new ListNode(400, node5);
35.         ListNode node3 = new ListNode(300, node4);
36.         ListNode node2 = new ListNode(200, node3);
37.         ListNode node1 = new ListNode(100, node2);
38.         ListNode prev = reserse(node1);
39.         System.out.println(prev.val);
40.         System.out.println(prev.next.val);
42.     }
43. }

复制代码

测试代码运行效果

解法二：递归

递归的思绪实在就是把一个大题目分成许多个小题目，然后探求到办理办法以后，再将方法推广到全局。
步调

1、通过头部节点，不绝地遍历，直到next指针指向为null，找到末了一个元素

2、如果遇到末了一个元素，则返回。接着将末了一个元素指向倒数第二个元素，而且将倒数第二个元素的指向更换成null，然后继续返回，以此类推

完备代码

下列是完备代码，包罗测试代码

1. package com.cys.algorithm;
3. public class ReverseList {
5.     static class ListNode {
6.         int val;
7.         ListNode next;
9.         public ListNode(int val, ListNode next) {
10.             this.val = val;
11.             this.next = next;
12.         }
13.     }
15.     public static ListNode reserse(ListNode head) {
16.         if (head == null || head.next == null){
17.             return head;
18.         }
19.         ListNode newHead = reserse1(head.next);
20.         head.next.next = head;
21.         head.next = null;
22.         return newHead;
23.     }
25.     public static void main(String[] args) {
26.         ListNode node5 = new ListNode(500, null);
27.         ListNode node4 = new ListNode(400, node5);
28.         ListNode node3 = new ListNode(300, node4);
29.         ListNode node2 = new ListNode(200, node3);
30.         ListNode node1 = new ListNode(100, node2);
31.         ListNode prev = reserse(node1);
32.         System.out.println(prev.val);
33.         System.out.println(prev.next.val);
35.     }
36. }

复制代码

测试代码运行效果