題目
給定一個(gè)鏈表垃帅，兩兩交換其中相鄰的節(jié)點(diǎn)中姜，并返回交換后的鏈表。
示例:
給定 1->2->3->4, 你應(yīng)該返回 2->1->4->3.
思路
我們首先需要建立pre晓褪、node1堵漱、node2和lat四個(gè)指針,然后pre->next=node2;node2.next=node1;node1.next=lat.
-----------
| |
h 1 <- 2 -> 3 -> 4
| |
-----------
listNode.h
#pragma once
#include <cstddef>
#include <iostream>
using namespace std;
/**Definition for singly-linked list.*/
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class ListNodeOperate
{
public:
/*
* 函數(shù)：在鏈表中插入值
* 輸入：原鏈表，插入值
*/
void insertNode(ListNode* p, int i);
/*
*函數(shù)：輸出鏈表
*輸入：待輸出鏈表
*/
void coutRes(ListNode* result);
};
listNode.cpp
#include "listNode.h"
void ListNodeOperate::insertNode(ListNode* p, int i)
{
ListNode* node = new ListNode(1);
node->val = i;
node->next = p->next;
p->next = node;
}
void ListNodeOperate::coutRes(ListNode* result)
{
ListNode* node = new ListNode(NULL);
node = result;
if (node != NULL)
{
do
{
cout << node->val << " ";
node = node->next;
} while (node != NULL);
}
}
solution
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* pre = NULL;
ListNode* Node1 = NULL;
ListNode* Node2 = NULL;
ListNode* lat = NULL;
ListNode* h = new ListNode(-1);
h->next = head;
pre = h;
while (pre->next != NULL && pre->next->next != NULL)
{
Node1 = pre->next;
Node2 = Node1->next;
lat = Node2->next;
pre->next = Node2;
Node2->next = Node1;
Node1->next = lat;
pre = Node1;
}
return h->next;
}
};
int main(int argc, char* argv[])
{
int a[] = { 1, 2, 3, 4 };
ListNode* test = new ListNode(NULL);
ListNode* result;
for (int i : a)
{
ListNodeOperate().insertNode(test,i);
}
result = Solution().swapPairs(test);
ListNodeOperate().coutRes(result);
system("pause");
return 0;
}
