【题目】
Given a linked list, swap every two adjacent nodes and return its head.
For example,
Given1->2->3->4
, you should return the list as2->1->4->3
.
Your algorithm should use only constant space. You maynotmodify the values in the list, only nodes itself can be changed.
【题意】
给定一个链表,交换每两个相邻的节点,并返回它的头。
你的算法应该使用常数空间。您不得修改在列表中的值,只有节点本身是可以改变的。
【分析】
无
【代码】
/*********************************
* 日期:2014-01-29
* 作者:SJF0115
* 题号: 24.Swap Nodes in Pairs
* 来源:http://oj.leetcode.com/problems/swap-nodes-in-pairs/
* 结果:AC
* 来源:LeetCode
* 总结:
**********************************/
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode *swapPairs(ListNode *head) {
if (head == NULL){
return head;
}
ListNode *dummy = (ListNode*)malloc(sizeof(ListNode));
dummy->next = head;
ListNode *nodeA,*nodeB = NULL;
ListNode *pre = dummy,*cur = head;
//至少2个节点采用交换
while(cur != NULL && cur->next != NULL){
nodeA = cur;
nodeB = cur->next;
//交换
nodeA->next = nodeB->next;
nodeB->next = nodeA;
pre->next = nodeB;
//更新pre,cur
pre = nodeA;
cur = nodeA->next;
}
return dummy->next;
}
};
int main() {
Solution solution;
int A[] = {1,2,3,4,5};
ListNode *head = (ListNode*)malloc(sizeof(ListNode));
head->next = NULL;
ListNode *node;
ListNode *pre = head;
for(int i = 0;i < 4;i++){
node = (ListNode*)malloc(sizeof(ListNode));
node->val = A[i];
node->next = NULL;
pre->next = node;
pre = node;
}
head = solution.swapPairs(head->next);
while(head != NULL){
printf("%d ",head->val);
head = head->next;
}
return 0;
}
【代码2】
class Solution {
public:
ListNode *swapPairs(ListNode *head) {
return reverseKGroup(head,2);
}
private:
ListNode *reverseKGroup(ListNode *head, int k) {
if (head == NULL || k < 2){
return head;
}
ListNode *dummy = (ListNode*)malloc(sizeof(ListNode));
dummy->next = head;
ListNode *pre = dummy,*cur = NULL,*tail = NULL;
//统计节点个数
int count = 0;
while(pre->next != NULL){
pre = pre->next;
count++;
}
//反转次数
int rCount = count / k;
int index = 0;
//反转元素的前一个
pre = dummy;
//反转元素第一个即翻转后的尾元素
tail = dummy->next;
//共进行rCount次反转
while(index < rCount){
int i = k - 1;
//反转
while(i > 0){
//删除cur元素
cur = tail->next;
tail->next = cur->next;
//插入cur元素
cur->next = pre->next;
pre->next = cur;
i--;
}
pre = tail;
tail = pre->next;
index++;
}
return dummy->next;
}
};
利用:
LeetCode之Reverse Nodes in k-Group
分享到:
相关推荐
用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现...
第四章 Leetcode 题解 1. Two Sum 2. Add Two Numbers 3. Longest Substring Without Repeating Characters 4. Median of Two Sorted Arrays...24. Swap Nodes in Pairs 25. Reverse Nodes in k-Group 26. Remove Dupli
JVM 基础 JAVA 并发 JVM 性能调优 LeetCode 算法 .......
My Solutions to Leetcode Database problems. 我的 Leetcode 数据.zip
Leetcode 题解.pdf
LeetCode 后端.zip
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101.zip
Leetcode101.zip
Recording personal Java, Python, JavaScript solutions for Leetcode problems. 记录个人 Java, Python, JavaScript 的Leetcode题解.zip
原创:leetcode 111. 二叉树的最小深度记住:最小深度和最大深度方法不同。* Definition for a binary tree node.in
刷leetcode总结.md
原创:leetcode 107. 二叉树的层次遍历 II【队列】* Definition for a binary tree node.
原创:leetcode 5. 最长回文子串//寻找以i-1,i为中点偶数长度的回文//寻找以i为中心的奇数长度的回文。
My Solutions to Leetcode problems. All solutions support C
原创:leetcode 22.括号生成【回溯】对待这种问题,千万别暴力搜索,那样太笨了。但是这个方法是最容易理解的//回溯法 (后面的括号) 不可以大于 (前面
LeetCode674. 最长连续递增序列674. 最长连续递增序列解题思路:记录每次递增序列的长度,max存储最大长度// 递增序列更新最大长度} else
leetcode-editor,在ide中做leetcode练习,支持leetcode.com和leetcode-cn.com,以满足练习的基本需求。理论上支持:intellij idea phpstorm webstorm pycharm rubymine appcode clion goland datagrip rider mps ...
LeetCode746.使用最小花费爬楼梯746. 使用最小花费爬楼梯解题思路:动态规划当前楼梯最小值=Math.min(前一步最小值,前两步最小值)简化 mi