原题链接: http://oj.leetcode.com/problems/swap-nodes-in-pairs/
Given a linked list, swap every two adjacent nodes and return its head. For example, Given 1->2->3->4, you should return the list as 2->1->4->3. Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed
struct ListNode* swapPairs(struct ListNode* head)
Q1 Given 1->2->3->4, you should return the list as 2->1->4->3 head指向第一个元素 1 函数指针传递是传递 无论如何交换参数head 不可能返回指向元素2 如何解决?
Q2: 链表遍历操作 ptr(A)=ptr->next(B) 前提条件节点A和节点B 位置关系没有发现变化 在链表排序(交换位置是排序一个方法)原来位置发生改变如何处理 ?
第一次循环处理结果: root: 0 ->1->2->3 ->4 之前 pre=0 cur=1 root: 0 ->2->1->3->4 之后 pre=1 cur=3 pre相对于原来排序移动2次
/** * 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) { //head节点 ListNode root(0); root.next =head; ListNode * pre=&root;//0 ListNode * cur =head;//1 while(cur && cur->next) { //swap pre->next=cur->next;// 0 --> 2 cur->next=pre->next->next;//1 --> 3 pre->next->next=cur;//2->1 pre=cur;// 虽然 pre 仍然指向 位置1 原来位置1 swap之后放到位置2后面 cur=cur->next;//pre ->1 cur->3 节 //0 ->2->1->3->4 } return root.next; } };
执行行效率分析: https://leetcode.com/submissions/detail/102239317/
耗时6ms不是最优解呀 耗时应该在建立头节点 如果不用头节点 需要特殊处理 第一次处理时候null 查看耗时3秒的 提取到函数外面 为了防止异常数据 异常判断
为了完成遍历 采用三个节点 first second three 三个节点
可以采用递归方式
参照历史题目:
本文分享自微信公众号 - 架构说(JiaGouS),作者:单链表
原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。
原始发表时间:2017-05-08
本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。
我来说两句