leetcode 24 Swap Nodes in Pairs

heartFollower 發(fā)布于2019-08-15 14:44 / 579人閱讀

摘要：最后返回頭節(jié)點(diǎn)。同時(shí)題目要求只能占用常數(shù)空間，并且不能改變節(jié)點(diǎn)的值，改變的是節(jié)點(diǎn)本身的位置。翻轉(zhuǎn)是以兩個(gè)節(jié)點(diǎn)為單位的，我們新聲明一個(gè)節(jié)點(diǎn)表示當(dāng)前操作到的位置。每次操作結(jié)束，將指針后移兩個(gè)節(jié)點(diǎn)即可。執(zhí)行操作前要確定操作的兩個(gè)節(jié)點(diǎn)不為空。

題目詳情

Given a linked list, swap every two adjacent nodes and return its head.題目要求輸入一個(gè)鏈表，我們將相鄰的兩個(gè)節(jié)點(diǎn)的順序翻轉(zhuǎn)。最后返回頭節(jié)點(diǎn)。同時(shí)題目要求只能占用常數(shù)空間，并且不能改變節(jié)點(diǎn)的值，改變的是節(jié)點(diǎn)本身的位置。
例如,
輸入 1->2->3->4, 你應(yīng)該返回的鏈表：2->1->4->3.

想法

要求返回頭節(jié)點(diǎn)，因此我們需要新建一個(gè)節(jié)點(diǎn)(dummy)指向頭節(jié)點(diǎn)，方便最后返回頭節(jié)點(diǎn)。

翻轉(zhuǎn)是以兩個(gè)節(jié)點(diǎn)為單位的，我們新聲明一個(gè)節(jié)點(diǎn)current表示當(dāng)前操作到的位置。每次操作結(jié)束，將current指針后移兩個(gè)節(jié)點(diǎn)即可。

執(zhí)行操作前要確定操作的兩個(gè)節(jié)點(diǎn)不為空。

簡(jiǎn)單畫了一下翻轉(zhuǎn)的過程

解法

    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode current = dummy;
        
        while(current.next != null && current.next.next != null){
            ListNode first = current.next;
            ListNode second = current.next.next;
            
            first.next = second.next;
            second.next = first;
            current.next = second;
            current = current.next.next;
        }
        
        return dummy.next;
    }