題目描述

給定一個(gè)鏈表，兩兩交換其中相鄰的節(jié)點(diǎn)，并返回交換后的鏈表。

你不能只是單純的改變節(jié)點(diǎn)內(nèi)部的值，而是需要實(shí)際的進(jìn)行節(jié)點(diǎn)交換。

示例:

給定 1->2->3->4, 你應(yīng)該返回 2->1->4->3.

我的方法：

看起來(lái)并不算很難，重點(diǎn)應(yīng)該在于理順整個(gè)處理流程。

1. 將節(jié)點(diǎn)分為兩兩一組，每次處理兩個(gè)節(jié)點(diǎn)。
2. 對(duì)于頭兩個(gè)節(jié)點(diǎn)，交換兩個(gè)節(jié)點(diǎn)后，只需要考慮整體的之后節(jié)點(diǎn)即可。
3. 對(duì)于中間的節(jié)點(diǎn)，交換兩個(gè)節(jié)點(diǎn)后，要考慮整體之前的節(jié)點(diǎn)以及整體之后的節(jié)點(diǎn)。
4. 如果最終有節(jié)點(diǎn)落單，則不進(jìn)行交換操作。

戰(zhàn)績(jī)一般：執(zhí)行用時(shí) : 32 ms, 在Swap Nodes in Pairs的Python提交中擊敗了9.28% 的用戶。內(nèi)存消耗 : 11.6 MB, 在Swap Nodes in Pairs的Python提交中擊敗了0.00% 的用戶。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head is None or head.next is None:
            return head
        # 如果長(zhǎng)度在2以上
        p=head.next
        pre=None
        # 遍歷鏈表
        while head:
            # 兩兩節(jié)點(diǎn)為一組，進(jìn)行處理
            a=head
            b=a.next
            if b:
                head=b.next #鏈表要持續(xù)移動(dòng)
                #交換兩個(gè)節(jié)點(diǎn)
                if pre:
                    pre.next=b
                    b.next=a
                else:
                    b.next=a
                a.next=None #不要形成環(huán)鏈
                pre=a
            else:
                head=b#鏈表要持續(xù)移動(dòng)
                if pre:
                    pre.next=a
        return p

別人的方法：

看了下別人的方法，確實(shí)很簡(jiǎn)潔?？雌饋?lái)是用的遞歸，沒錯(cuò)，這個(gè)問(wèn)題用遞歸解決很適合。

class Solution(object):
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
        
        chead = self.swapPairs(head.next.next)
        hnext = head.next
        head.next, hnext.next = chead, head
        return hnext