题目:将链表的奇数位和偶数位调换组成新的链表

题目:将链表的奇数位和偶数位调换组成新的链表

原题链接: 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 如何解决?

  • 必须重新建立一个新的链表 进行返回
  • 采用 带头节点单链表 知识补充:带头节点单链表和不带头节点单链表有什么区别 带头结点单链表好处解决了 不用判断第一个节点是否为空 不需要特殊处理 用统一方法实现就 例如 链表insert操作** 返回值是最新链表 struct ListNode* head 不是

Q2: 链表遍历操作 ptr(A)=ptr->next(B) 前提条件节点A和节点B 位置关系没有发现变化 在链表排序(交换位置是排序一个方法)原来位置发生改变如何处理 ?

  • 需要临时遍历记录 下 B位置
  • 链表交换节点 影响不是2个 而是三个 不要忘记最后 1 -2-3 A=2 B=3 2-1-3 A=2 B=1 >>A=1 B=3 解题思路如下

第一次循环处理结果: root: 0 ->1->2->3 ->4 之前 pre=0 cur=1 root: 0 ->2->1->3->4 之后 pre=1 cur=3 pre相对于原来排序移动2次

code

/**
 * 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)

原文发表时间:2017-05-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java进阶架构师

对HashMap的思考及手写实现

HashMap是Java中常用的集合,而且HashMap的一些思想,对于我们平时解决业务上的一些问题,在思路上有帮助,基于此,本篇博客将分析HashMap底层设...

10820
来自专栏王磊的博客

Java核心(四)面试必备—你不知道的数据集合

导读:Map竟然不属于Java集合框架的子集?队列也和List一样属于集合的三大子集之一?更有队列的正确使用姿势,一起来看吧!

10620
来自专栏LanceToBigData

Java集合源码分析(三)Vevtor和Stack

前言   前面写了一篇关于的是LinkedList的除了它的数据结构稍微有一点复杂之外,其他的都很好理解的。这一篇讲的可能大家在开发中很少去用到。但是有的时候也...

25960
来自专栏皮皮之路

【JDK1.8】JDK1.8集合源码阅读——Set汇总

322120
来自专栏Java学习网

Java中三种Set类型用法、性能大比拼

Java为开发者提供了大量的工具类,这给开发人员带来了很大方便,但是选择多了也有困扰,究竟用哪个类;我想选择什么,一是看自己具体需求,二是类本身的性能和用法;J...

88060
来自专栏项勇

笔记72 | 将姓放在名的后面,排序按姓氏首字母排列的修改笔记

19450
来自专栏coolblog.xyz技术专栏

LinkedHashMap 源码详细分析(JDK1.8)

LinkedHashMap 继承自 HashMap,在 HashMap 基础上,通过维护一条双向链表,解决了 HashMap 不能随时保持遍历顺序和插入顺序一致...

507100
来自专栏java思维导图

【一分钟知识】HashSet和TreeSet,HashMap与HashTable

java思维导图 xmind导图配合精美文章,可视化学习,让java不再难懂。 ? ? HashSet和TreeSet HashSet 哈希表实现的,HashS...

36970
来自专栏desperate633

LeetCode Delete Node in a Linked ListQuestion题目分析代码

给定一个单链表中的一个等待被删除的节点(非表头或表尾)。请在在O(1)时间复杂度删除该链表节点。

8730
来自专栏恰童鞋骚年

剑指Offer面试题:24.复杂链表的复制

  下图是一个含有5个结点的复杂链表。图中实线箭头表示m_pNext指针,虚线箭头表示m_pSibling指针。为简单起见,指向NULL的指针没有画出。

8720

扫码关注云+社区

领取腾讯云代金券