链表与递归一、

链表与递归的渊源一

链表的常见问题

LeetCode 24、两两交换链表中的节点 https://leetcode-cn.com/problems/swap-nodes-in-pairs/

通常，在解决关于链表这类问题，我们会设置一个虚拟头节点，这样可以为我们省去判断头节点的很多麻烦。

先来讲一下本题的常规解法。

1、我们初始化三个指针pre,cur,future，分别指向dummy,head,以及head.next。

如图所示，我们分为三个步骤，经过该步骤，链表变为了 2->1->3->4。很明显，我们只要重复进行该步骤即可。

当进行完一轮交换后，我们需要交换3 和4这两个节点，此时我们的pre指针应该向前移两步。

即此时pre,cur,future指针应该分别指向2,3,4。如果链表中有奇数个节点也没有关系，只要cur指针及他下一个位置不为空，我们都可以进行交换。

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy=new ListNode(0);
         dummy.next=head;
          //初始化三个指针
         ListNode pre=dummy; 
         while(pre.next!=null&&pre.next.next!=null){
             ListNode cur=pre.next;
              ListNode future=pre.next.next;
             //1、dummy->第二个节点
             pre.next=future;
             //2、第一个节点->第三个节点
              cur.next=future.next;
             //3、第二个节点->第一个节点
             future.next=cur;
             //往后移两格
             pre=pre.next.next;
         }
         return dummy.next;
    }
}

有了上述的思路，代码也非常简单,如上所述。

接下来我们用递归的方式来解决这个问题

• 由于链表的天然属性，我们可以很自然的将其与递归联系到一起。可能说到递归，大家首先想到的是树这个结构，其实不然，链表也和递归紧密关联着。
• 递归不就是将原来的问题，转化为一个更小的问题去解决吗？
• 链表的天然递归性在于：0->1->2->3->4这个链表可以变为 0-> 和一个少了一个节点的链表。

下面说用递归解决的思路

• 我们将链表想象成三个部分。 head->head.next->交换后的链表
• 使用递归的好处就是，我们不必去关心细节是怎样实现的，对于本题而言，我们不必去关心head.next后面是如何交换的，我们只需要交换head和head.next就行。
• 本题中，递归函数的作用就是：两两交换链表中的节点，这是我们需要关注的。
• 接下来看递归终止条件：当只有一个节点，或者该节点为空时，递归应该终止.

class Solution {
    public ListNode swapPairs(ListNode head) {
       if(head==null||head.next==null) return head;
       ListNode future=head.next;
       head.next= swapPairs(future.next);
       future.next=head;
       return future;
    }
}

通过递归，我们不必去深究后面的子链表是如何实现交换的，我们只用交换这两个节点，非常简单！

LeetCode203、移除链表元素. https://leetcode-cn.com/problems/remove-linked-list-elements/

先说常规思路

• 要想删除链表元素，最简单的方法就是找到待删除元素的前一个节点，然后进行删除操作
• 对于本题我们可以进行一次遍历操作.

class Solution {
    public ListNode removeElements(ListNode head, int val) {
          ListNode dummy=new ListNode(0);
          dummy.next=head;
          ListNode pre=dummy;
          while(pre.next!=null){
            if(pre.next.val==val){
                //删除操作,跳过该元素即可
                pre.next=pre.next.next;
            }else{
                pre=pre.next;
            }
          }
          return dummy.next;
    }
}

这样做，也是非常简单的！

接下来说一下递归的思路

• 像刚才一样，链表具有天然的递归性质，在本题，我们只需要将链表想象成 头节点->处理完的链表即可.
• 我们不必去关心后面处理完的链表的删除操作是如何进行的，我们只用关心头节点需不需要删除即可.
• 递归的终止条件，当链表为空时，递归终止.

class Solution {
    public ListNode removeElements(ListNode head, int val) {
         if(head==null) return null;
        head.next=removeElements(head.next,val);
        return head.val==val?head.next:head;

    }
}

如果使用递归，我们的代码将会变得非常整洁，同样也非常简单！

LeetCode 206、反转链表 https://leetcode-cn.com/problems/reverse-linked-list/

先说常规思路

我们额外声明一个节点，然后遍历整个链表，当遍历到第一个节点时，就将他挂接到这个新节点上。然后改变头节点的位置，重复进行该步骤。

class Solution {
    public ListNode reverseList(ListNode head) {
           ListNode pre = null; //前指针节点
        ListNode cur = head; //当前指针节点
        //每次循环，都将当前节点指向它前面的节点，然后当前节点和前节点后移
        while (cur != null) {
            ListNode temp = cur.next; //临时节点，暂存当前节点的下一节点，用于后移
            cur.next = pre; //将当前节点指向它前面的节点
            pre = cur; //前指针后移
            cur = temp; //当前指针后移
        }
        return pre;
    }
}

这样看起来，还是比较绕，不用担心，接下来用递归来解决该问题.

递归的思路

• 我们将这个链表看为1->和已经处理好的链表。
• 如果需要反转的链表为 1->2->3->4->5，即此时应该为 1->5->4->3->2
• 我们只需要将1挂接到2的后面即可。
• 递归的终止条件，当头节点为空，或者头节点的下一个元素为空时，递归终止。

class Solution {
    public ListNode reverseList(ListNode head) {
          if(head==null||head.next==null) return head;
        ListNode newNode=  reverseList(head.next);
        head.next.next=head;
        head.next=null;
        return newNode;
    }
}

相信通过这三题，你对链表问题已经递归的初步使用已经有了一个初步印象。

赏

谢谢你请我喝奶茶

微信