Problem

Given a linked list, swap every two adjacent nodes and return its head.

You may not modify the values in the list's nodes, only nodes itself may be changed.
我的博客: hanielxx.com
文章原文: LeetCode-024-Swap Nodes in Pairs

Examples:

Input: 1-2-3-4
Output: 2-1-4-3

Solutions

• 很直接的, 每兩個節(jié)點交換一下順序, 可以遞歸但是并不需要.
• 指針之間的交換要注意不要漏了某個next的賦值, 可能會導致出現(xiàn)環(huán)
• 多指針的題目寧愿多弄幾個變量, 更清楚, 而不是一直next, next這樣賦值

C++ Codes

非遞歸做法
8ms, 一般般把, 題目不是特別復雜

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(head==NULL || head->next==NULL)return head;
        ListNode* q=head->next;
        ListNode *t, *s, *tmp;
        t=q->next;//第三個節(jié)點
        //交換第一第二節(jié)點, head->q 變?yōu)閝->head, 然后q等于第二個節(jié)點
        q->next=head;
        head->next=t;
        head=q;
        q=head->next;
        //1234, 此時變?yōu)?134, q->val=1, t->val=3, s->val=4, tmp=NULL
        while(t!=NULL && t->next!=NULL){
            s=t->next;
            //tmp用于t的迭代
            tmp=s->next;
            //令q->next等于第四個節(jié)點, 且交換3, 4節(jié)點, t->s變成s->t
            q->next=s;
            s->next=t;
            //這步防止t和s形成環(huán), t->next==s, s->next==t
            t->next=tmp;
            //更新q和t
            q=t;
            t=tmp;
        }
        return head;
    }
};

遞歸做法

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

        ListNode *p1 = head;
        ListNode *p2 = p1->next;

        p1->next = swapPairs(p2->next);
        p2->next = p1;

        return p2;
    }
};

Python Codes

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        pre = ListNode(0)
        p = pre
        h = head
        while h:
            if h and h.next:
                tmp = h.next
                p.next = tmp
                h.next = h.next.next
                tmp.next = h
                h = h.next
                p = p.next.next
            else:
                p.next = h
                h = h.next
        return pre.next

總結

• 鏈表指針操作要注意別出現(xiàn)環(huán)