Swift 算法实战之路:链表

[中文教程]
分享到:  QQ好友和群QQ好友和群 QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友 微信微信
查看查看133 回复回复2 收藏收藏 分享淘帖 转播转播 分享分享 微信
查看: 133|回复: 2
收起左侧

[中文教程] Swift 算法实战之路:链表

[复制链接]
代码买卖 发表于 2016-9-7 03:33:24 | 显示全部楼层 |阅读模式
快来登录
获取最新的苹果动态资讯
收藏热门的iOS等技术干货
拷贝下载Swift Demo源代码
本帖最后由 代码买卖 于 2016-9-7 04:06 编辑


上期我们探讨了使用Swift如何破解数组、字符串、集合、字典相关的算法题。本期我们一起来讲讲用Swift如何实现链表以及链表相关的技巧。本期主要内容有:

  • 链表基本结构
  • Dummy节点
  • 尾插法
  • 快行指针


Swift 算法实战之路:链表 1

Swift 算法实战之路:链表 - 敏捷大拇指 - Swift 算法实战之路:链表 1





1、基本结构

对于链表的概念,实在是基本概念太多,这里不做赘述。我们直接来实现链表节点。

[Swift] 纯文本查看 复制代码
class ListNode {
  var val: Int
  var next: ListNode?

  init(_ val: Int) {
    self.val = val
    self.next = nil
  }
}


有了节点,就可以实现链表了。

[Swift] 纯文本查看 复制代码
class List {
  var head: ListNode?
  var tail: ListNode?

  // 尾插法
  func appendToTail(val: Int) {
    if tail == nil {
      tail = ListNode(val)
      head = tail
    } else {
      tail!.next = ListNode(val)
      tail = tail!.next
    }
  }

  // 头插法
  func appendToHead(val: Int) {
    if head == nil {
      head = ListNode(val)
      tail = head
    } else {
      let temp = ListNode(val)
      temp.next = head
      head = temp
    }
  }
}


有了上面的基本操作,我们来看如何解决复杂的问题。




2、Dummy节点和尾插法

话不多说,我们直接先来看下面一道题目。

给一个链表和一个值x,要求将链表中所有小于x的值放到左边,所有大于等于x的值放到右边。原链表的节点顺序不能变。

例:1->5->3->2->4->2,给定x = 3。则我们要返回 1->2->2->5->3->4

直觉告诉我们,这题要先处理左边(比x小的节点),然后再处理右边(比x大的节点),最后再把左右两边拼起来。

思路有了,再把题目抽象一下,就是要实现这样一个函数:

[Swift] 纯文本查看 复制代码
func partition(head: ListNode?, _ x: Int) -> ListNode? {}


即我们有给定链表的头节点,有给定的x值,要求返回新链表的头结点。接下来我们要想:怎么处理左边?怎么处理右边?处理完后怎么拼接?

先来看怎么处理左边。我们不妨把这个题目先变简单一点:

给一个链表和一个值x,要求只保留链表中所有小于x的值,原链表的节点顺序不能变。

例:1->5->3->2->4->2,给定x = 3。则我们要返回 1->2->2

我们只要采用尾插法,遍历链表,将小于x值的节点接入新的链表即可。代码如下:

[Swift] 纯文本查看 复制代码
func getLeftList(head: ListNode?, _ x: Int) -> ListNode? {
  let dummy = ListNode(0)
  var pre = dummy
  var node = head

  while node != nil {
    if node!.val < x {
      pre.next = node
      pre = node!
    }
    node = node!.next
  }
  return dummy.next
}


注意,上面的代码我们引入了Dummy节点,它的作用就是作为一个虚拟的头前结点。我们引入它的原因是我们不知道要返回的新链表的头结点是哪一个,它有可能是原链表的第一个节点,可能在原链表的中间,也可能在最后,甚至可能不存在(nil)。而Dummy节点的引入可以巧妙的涵盖所有以上情况,我们可以用dummy.next方便得返回最终需要的头结点。

现在我们解决了左边,右边也是同样处理。接着只要让左边的尾节点指向右边的头结点即可。全部代码如下:

[Swift] 纯文本查看 复制代码
func partition(head: ListNode?, _ x: Int) -> ListNode? {
  // 引入Dummy节点
  let prevDummy = ListNode(0)
  var prev = prevDummy
  let postDummy = ListNode(0)
  var post = postDummy

  var node = head

  // 用尾插法处理左边和右边
  while node != nil {
    if node!.val < x {
      prev.next = node
      prev = node!
    } else {
      post.next = node
      post = node!
    }     
    node = node!.next
  }

  // 左右拼接
  post.next = nil
  prev.next = postDummy.next

  return prevDummy.next
}


注意这句post.next = nil,这是为了防止链表循环指向构成环,是必须的但是很容易忽略的一步。

刚才我们提到了环,那么怎么检测链表中是否有环存在呢?

Swift 算法实战之路:链表 2

Swift 算法实战之路:链表 - 敏捷大拇指 - Swift 算法实战之路:链表 2





3、快行指针

笔者理解快行指针,就是两个指针访问链表,一个在前一个在后,或者一个移动快另一个移动慢,这就是快行指针。所以如何检测一个链表中是否有环?用两个指针同时访问链表,其中一个的速度是另一个的2倍,如果他们相等了,那么这个链表就有环了。代码如下:

[Swift] 纯文本查看 复制代码
func hasCycle(head: ListNode?) -> Bool {
  var slow = head
  var fast = head

  while fast != nil && fast!.next != nil {
    slow = slow!.next
    fast = fast!.next!.next

    if slow === fast {
      return true
    }
  }

  return false
}


再举一个快行指针一前一后的例子,看下面这道题。

删除链表中倒数第n个节点。例:1->2->3->4->5,n = 2。返回1->2->3->5。

注意:给定n的长度小于等于链表的长度。

解题思路依然是快行指针,这次两个指针移动速度相同。但是一开始,第一个指针(指向头结点之前)就落后第二个指针n个节点。接着两者同时移动,当第二个移动到尾节点时,第一个节点的下一个节点就是我们要删除的节点。代码如下:

[Swift] 纯文本查看 复制代码
func removeNthFromEnd(head: ListNode?, _ n: Int) -> ListNode? {
  guard let head = head else {
    return nil
  }

  let dummy = ListNode(0)
  dummy.next = head
  var prev: ListNode? = dummy
  var post: ListNode? = dummy

  // 设置后一个节点初始位置
  for _ in 0 ..< n {
    if post == nil {
      break
    }
    post = post!.next
  }

  // 同时移动前后节点
  while post != nil && post!.next != nil {
    prev = prev!.next
    post = post!.next
  }

  // 删除节点
  prev!.next = prev!.next!.next

  return dummy.next
}


这里还用到了Dummy节点,因为有可能我们要删除的是头结点。




4、总结

这次我们用Swift实现了链表的基本结构,并且实战了链表的几个技巧。在结尾处,我还想强调一下Swift处理链表问题的两个细节问题:

  • 一定要注意头结点可能就是nil。所以给定链表,我们要看清楚head是不是optional,在判断是不是要处理这种边界条件。
  • 注意每个节点的next可能是nil。如果不为nil,请用"!"修饰变量。在赋值的时候,也请注意"!"将optional节点传给非optional节点的情况。


下一次我们讨论栈和队列




相关内容

Swift 算法实战之路:基本语法与技巧

Swift 算法实战之路:数组,字符串,集合,与字典

Swift 算法实战之路:链表

Swift 算法实战之路:栈和队列

Swift 算法实战之路:二叉树

Swift 算法实战之路:排序

Swift 算法实战之路:二分搜索

Swift 算法实战之路:深度和广度优先搜索

Swift 算法实战之路:动态规划




作者:故胤道长

都看到这里了,就把这篇资料推荐给您的好朋友吧,让他们也感受一下。

回帖是一种美德,也是对楼主发帖的尊重和支持。

*声明:敏捷大拇指是全球最大的Swift开发者社区、苹果粉丝家园、智能移动门户,所载内容仅限于传递更多最新信息,并不意味赞同其观点或证实其描述;内容仅供参考,并非绝对正确的建议。本站不对上述信息的真实性、合法性、完整性做出保证;转载请注明来源并加上本站链接,敏捷大拇指将保留所有法律权益。如有疑问或建议,邮件至marketing@swifthumb.com

*联系:微信公众平台:“swifthumb” / 腾讯微博:@swifthumb / 新浪微博:@swifthumb / 官方QQ一群:343549891(满) / 官方QQ二群:245285613 ,需要报上用户名才会被同意进群,请先注册敏捷大拇指

嗯,不错!期待更多好内容,支持一把:
支持敏捷大拇指,用支付宝支付10.24元 支持敏捷大拇指,用微信支付10.24元

评分

参与人数 1金钱 +10 贡献 +10 专家分 +10 收起 理由
Anewczs + 10 + 10 + 10 32个赞!专家给力!

查看全部评分

本帖被以下淘专辑推荐:

Caesar 发表于 2016-9-7 22:07:21 | 显示全部楼层
求实用场景
i0n1c 发表于 2016-10-13 03:09:07 | 显示全部楼层
这一系列通俗易懂啊
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

做任务,领红包。
我要发帖

分享扩散

都看到这里了,就把这资料推荐给您的好朋友吧,让他们也感受一下。
您的每一位朋友访问此永久链接后,您都将获得相应的金钱积分奖励
热门推荐

合作伙伴

Swift小苹果

  • 北京治世天下科技有限公司
  • ©2014-2016 敏捷大拇指
  • 京ICP备14029482号
  • Powered by Discuz! X3.1 Licensed
  • swifthumb Wechat Code
  •   
快速回复 返回顶部 返回列表