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

leetcode链接：
https://leetcode.cn/problems/swap-nodes-in-pairs/

方案一–遍历

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

        ListNode right = head.next;
        ListNode left = head;
        ListNode rightTemp = null;
        ListNode leftTemp = null;

        head = head.next;

        while (right != null && left != null) {
            rightTemp = right.next;

            right.next = left;
            left.next = rightTemp;
            
            if (leftTemp != null) {
                leftTemp.next = right;
            }

            leftTemp = left;
            left = rightTemp;

            if (left != null) {
                right = left.next;
            }
        }
        
        return head;
    }
}

Accepted

• 55/55 cases passed (0 ms)
• Your runtime beats 100 % of java submissions
• Your memory usage beats 90.36 % of java submissions (38.9 MB)

分析

时间复杂度：
O( n )

空间复杂度：
O( 1 )

方案二–迭代

参考：
https://leetcode.cn/problems/swap-nodes-in-pairs/solution/dong-hua-yan-shi-24-liang-liang-jiao-huan-lian-bia/

class Solution {
	public ListNode swapPairs(ListNode head) {
		//递归的终止条件
		if(head==null || head.next==null) {
			return head;
		}
		//假设链表是 1->2->3->4
		//这句就先保存节点2
		ListNode tmp = head.next;
		//继续递归，处理节点3->4
		//当递归结束返回后，就变成了4->3
		//于是head节点就指向了4，变成1->4->3
		head.next = swapPairs(tmp.next);
		//将2节点指向1
		tmp.next = head;
		return tmp;
	}
}

作者：wang_ni_ma
链接：https://leetcode.cn/problems/swap-nodes-in-pairs/solution/dong-hua-yan-shi-24-liang-liang-jiao-huan-lian-bia/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。