讨论/《递归》 - 两两交换链表中的节点/
《递归》 - 两两交换链表中的节点
共 8 个回复

C++ 反转

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(head==nullptr||head->next==nullptr) return head;
        ListNode* p=head->next;
        head->next=swapPairs(p->next);
        p->next=head;
        return p;
    }
};
9

1,非递归解决

这题主要考察的是链表节点的交换,要交换链表的节点首先要搞懂链表节点的断开和连接,之前写过一篇文章,《352,数据结构-2,链表》,图文详细介绍了单向链表,双向链表,还有环形链表的断开和链接。这道题我们可以人为的把链表分为两组,前面两个节点为一组,后面的为一组,我们首先交换第一组的两个节点,交换完之后把后面的节点再分为两组,继续这样交换下去……,直到不能交换为止。注意,如果能交换,那么原来链表的第二个节点就是我们要返回新链表的头结点。
这里就以示例为例画个图来看下
image.png

最后来看下代码

    public ListNode swapPairs(ListNode head) {
        //链表至少有2个节点才能交换,否则就不要交换
        if (head == null || head.next == null)
            return head;
        //这里的first,second,third可以参照图中的标注
        ListNode first = head;
        ListNode second;
        ListNode third;
        //这个是交换链表之后的尾结点,他的next要指向新交换的链表
        ListNode preLast = null;
        //这个只赋值一次,它是要返回的新链表的头结点
        ListNode newHead = head.next;
        //如果能交换就继续操作
        while (first != null && first.next != null) {
            //给second,third赋值
            second = first.next;
            third = second.next;
            //first和second这两个节点交换
            first.next = third;
            second.next = first;
            //这个时候second就是交换之后新链表的头结点,
            //如果preLast不为空,说明前面还有交换完成的链表
            //,要让preLast的next指向新链表的头结点
            if (preLast != null) {
                preLast.next = second;
            }
            //因为first和second交换之后,first就变成新链表
            //的尾结点了,把它保存在preLast中
            preLast = first;
            //前两个交换了,然后从第3个在继续操作
            first = third;
        }
        //返回新链表
        return newHead;
    }

看一下运行结果

image.png


2,递归解法

还可以改为递归的方式,代码中有详细注释

    public ListNode swapPairs(ListNode head) {
        //边界条件判断
        if (head == null || head.next == null)
            return head;
        //从第3个链表往后进行交换
        ListNode third = swapPairs(head.next.next);
        //从第3个链表往后都交换完了,我们只需要交换前两个链表即可,
        //这里我们把链表分为3组,分别是第1个节点,第2个节点,后面
        //的所有节点,也就是1→2→3,我们要把它变为2→1→3
        ListNode second = head.next;
        head.next = third;
        second.next = head;
        
        return second;
    }

看下运行结果
image.png


3,只交换节点的值

本来以为就这样写完了,再仔细看一下题的要求有这样一句话,你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。瞬间来了灵感,和题的要求对着干,只交换节点值,试一下能不能通过测试,结果还真通过了

    public ListNode swapPairs(ListNode head) {
        int first;
        ListNode temp = head;
        while (temp != null && temp.next != null) {
            //节点值的交换
            first = temp.val;
            temp.val = temp.next.val;
            temp.next.val = first;
            
            temp = temp.next.next;
        }
        return head;
    }

看下运行结果
image.png


我把部分算法题整理成了PDF文档,截止目前总共有900多页,大家可以下载阅读
链接https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码:6666

如果觉得有用就给个赞吧,还可以关注我的LeetCode主页查看更多的详细题解

7
class Solution {
public:
    //用来两两反转的函数
    ListNode* swapPairs(ListNode* head) {
        if(head == NULL || head -> next == NULL)
            return head;
        ListNode* newList = swapPairs(head -> next -> next);
        //反转节点
        ListNode* p = head -> next ;
        p -> next = head;
        head -> next = newList;
        return p;
    }
};
4
class Solution {
    public ListNode swapPairs(ListNode head) {
        return help(head);
    }

    public ListNode help(ListNode before){
        if(before == null || before.next == null){
            return before;
        }
        ListNode after = before.next;
        before.next = help(after.next);
        after.next = before;
        return after;
    }
}
1

这个实现还是挺巧妙的,关键是如果head有父指针,就不能简单的交换一下head和head.next的顺序,还需要让head的父指针指向head.next,这在递归里面将函数返回值赋给父指针即可。
第一次在java中使用“指针”,发现java中的“指针”就是类的成员属性。(请原谅我是个菜鸡)

class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null)    return null;
        if(head.next == null)  return head;
        ListNode pre = head;
        ListNode post = head.next;
        pre.next = swapPairs(post.next);
        post.next = pre;
        return post;
    }
}
class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head==null){
            return null;
        }
        return DFS(head,head.next);
    }
    public ListNode DFS(ListNode node,ListNode last){
        if(last==null){
            return node;//后面节点为空,返回前面一个
        }
        ListNode nextNode=null;
        node.next=nextNode;
        nextNode=node;
        ListNode temp=last.next;
        last.next=nextNode;
        if(temp==null){ //判断后面是否有节点
            return last;
        }
        nextNode.next=DFS(temp,temp.next);
        return last;
    }
}

主要是理清递归前后节点间的关系

public ListNode swapPairs(ListNode head) {
        if (head == null) return null;
        ListNode ln = new ListNode();
        ln.next = head;
        swap(head, ln);
        return ln.next;
    }

    public void swap(ListNode head, ListNode lastNode) {
        ListNode temp = null;
        if (head.next != null) {
            temp = head.next;
            head.next = temp.next;
            temp.next = head;
            lastNode.next = temp;
        }
        if (temp == null) {
            return;
        }
        if (temp.next.next != null) {
            swap(temp.next.next, temp.next);
        }
    }
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        return swap2(head);
    }

    ListNode* swap2(ListNode* head) {
        if(head == NULL || head->next == NULL) {
            return head;
        }
        ListNode *next2 = head->next->next;
        ListNode *tmpHead = head;
        head = head->next;
        head->next = tmpHead;
        head->next->next = swap2(next2);
        return head;
    }
};