LinkList5

发表于 更新于 分类于 ，

题目描述[原题描述][https://leetcode-cn.com/problems/swap-nodes-in-pairs/]

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例:

给定 1->2->3->4, 你应该返回 2->1->4->3.

算法描述

​ 要将链表的相邻的节点两两交换，交换链表要知道节点的前驱以及后继，后继节点可以通过next访问，前驱节点需要一个新节点来存起来，所以需要三个节点进行交换，注意交换顺序即可

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode * fakeHead = new ListNode(0);fakeHead->next=head;
        ListNode *first,*second,*third;
        first=fakeHead;
        while(first&&first->next&&first->next->next){
            second=first->next;
            third=second->next;
            second->next=third->next;
            first->next=third;
            third->next=second;
            first=second;
        }
        return fakeHead->next;
    }
};

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head==null||head.next==null)return head;
        ListNode d = new ListNode(0);
        d.next=head;
        ListNode frist,two,three;
        three=d;
        while(three!=null&&three.next!=null&&three.next.next!=null){
            two = three.next;
            frist = two.next;
            three.next = frist;
            two.next=frist.next;
            frist.next=two;
            three = two;
        }
        return d.next;
    }
}