力扣LeetCode-链表中的循环与递归使用

标题做题的时候发现循环与递归的使用差别：

看两道题：

两道题都是不知道链表有多长，所以需要用到循环，用到循环就可以把整个过程分成多个循环体，就是每一次循环要执行的内容。
反转链表：

把null–>1改为1–>null、1–>2改为2–>1。。。这些过程都是循环体程序，这里的问题是，链表的结构是单链，一个节点node包含val和next，每一次执行循环体需要交换两个节点的位置，并且需要留下头结点来给下一次循环体使用，比如：1和2交换位置由1–>2改为2–>1后你需要留下指向2的地址变量给下一次的循环体3和2交换的时候3的next指向2。
怎么留下上一次循环体的变量呢？直接在循环体外面定义一个全局变量，全局变量不会随着循环进行而改变。
于是有了以下的代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode temp = head;//temp用来推进循环的进行，也就是temp 会进行temp = temp.next。
        ListNode temp2 = null;//交换两个节点需要一个中间变量temp2来记录，这跟交换两个int是一样的，只不过这里换成了地址/引用
        ListNode pre_node = null;//全局变量，用来记录上一次循环体留下的变量给下一次循环体使用
        while(temp != null) {
            temp2 = temp.next;
            temp.next = pre_node;
            pre_node = temp;         
            temp = temp2;
        }
        return pre_node;


    }
}

两两交换链表中的节点，这里的每一次循环体很明显，交换两个节点的位置，1<–>2、3<–>4；但是循环体在交换后需要留下尾节点作为下一次循环体的头结点：

1和2交换之后需要把1节点的引用留给（3<–>4）节点作为头结点，但是这里节点的结构并没有双链结构，也就是节点没有办法接受/设置他的上一个节点，只能设置下一个节点next，所以是3和4交换后把头结点留给1和2做尾节点，这样子就是从链表的尾巴开始做起，这里循环也可以做，但是太麻烦了，麻烦就在循环条件的设定，因为头结点并没有双联结构，如果先去算出链表的长度，然后从链表尾巴开始两个两个交换，每次交换记录头结点也是可以的，但是这里从尾巴开始做起，而且下一个循环体的头结点留给上一个循环体使用，在链表的末尾有一个很好的循环结束条件：节点的next==null；这里就可以使用递归了。
代码如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {       
        if(head == null) {//递归结束条件
            return null;
        }
        if(head.next == null) {//应对只有一个节点的链表
            return head;
        }
        ListNode old_haed = swapPairs(head.next.next);//old_head是34留的头结点给12做尾节点
        ListNode temp_node = head;
        head = head.next;
        head.next = temp_node;
        head.next.next = old_haed;
        return  head;
    }
}

原文地址：https://blog.csdn.net/m0_49447039/article/details/142768230

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！