02链表：24、两两交换链表中的节点

互联网 10 月前 0 2

本文介绍: leetcode题目 24、两两交换链表中的节点

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

重点：构造虚拟节点，每两个一组进行循环处理

1. 迭代
1. 递归

方法一：迭代

    public ListNode swapPairs(ListNode head) {
        // 虚拟节点
        ListNode dumyhead = new ListNode(0);
        dumyhead.next = head;

        //当前节点
        ListNode cur = dumyhead;

        while (cur.next != null && cur.next.next != null) {
            //取出临时节点
            ListNode first=  cur.next;
            ListNode second = cur.next.next;
            ListNode third = cur.next.next.next;

            //替换
            cur.next = second;
            second.next = first;
            first.next = third;

            //更新指针（当前第二个位置是first）
            cur = first;
        }
        return dumyhead.next;
    }

方法二：递归

    public ListNode swapPairs(ListNode head) {
        // base case 退出提交
        if(head == null || head.next == null) return head;
        // 获取当前节点的下一个节点
        ListNode next = head.next;
        // 进行递归
        ListNode newNode = swapPairs(next.next);
        // 这里进行交换
        next.next = head;
        head.next = newNode;

        return next;
    }