24. 两两交换链表中的节点

发布时间:2023年12月27日

非递归方法(自己写的)

class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null)
            return head;
        ListNode dummy = new ListNode(0, head);
        ListNode pre = dummy;
        ListNode cur = head;
        while (cur != null && cur.next != null) {
            ListNode curNext = cur.next;
            cur.next = curNext.next;
            curNext.next = cur;
            pre.next = curNext;
            pre = cur;
            cur = cur.next;
        }
        return dummy.next;
    }
}

递归方法(看别人的)

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

递归思路

1. 找终止条件

当递归到链表为空或链表中只剩一个元素时。没有可以交换的节点,就终止递归

2.找返回值

返回给上一层的值应该是已经交换完成之后的子链表

3.单次的过程

因为递归时重复做一样的事,从宏观上讲,只考虑某一部是怎么完成的。
假设待交换的两个节点分别是head和next,next应该接受上一级返回的子链表。
就相当于是一个含有三个节点的链表交换前两个节点。
文章来源:https://blog.csdn.net/qq_44047415/article/details/135242670
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。