Swift Leetcode 链表 算法题解

1.移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

**示例 **

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

public class ListNode {
    public var val: Int
    public var next: ListNode?
    public init() { self.val = 0; self.next = nil; }
    public init(_ val: Int) { self.val = val; self.next = nil; }
    public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
}
func removeElements(_ head: ListNode?, _ val: Int) -> ListNode? {
        guard head != nil else { return head }
        //虚拟头结点 也是新链表的头结点
        let dummyHead = ListNode() 
        //新链表尾结点
        var newTail = dummyHead
       
        //用来遍历的链表头，swift传参都是不可变的
        var curHead = head

        //遍历链表
        while curHead != nil {
            if curHead?.val != val {
                newTail.next = curHead
                newTail = curHead!
            }
            curHead = curHead?.next
        }
        //尾部置空
        newTail.next = nil

        return dummyHead.next
    }

解题思路：
这里用一个虚拟头结点来作为新链表的头结点会让代码更加的简洁，遍历传进来的链表，判断当前的链表是否是需要删除的如果不是需要删除的，让新链表尾结点下一个指向它，也就是尾部结点也是当前结点，最后把尾部结点置空，返回新节点头的下一个结点。

2.两数相加

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头

示例 ：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

提示：

• 每个链表中的节点数在范围 [1, 100] 内

• 0 <= Node.val <= 9

• 题目数据保证列表表示的数字不含前导零

func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
          guard l1 != nil else { return l2 }
          guard l2 != nil else { return l1 }

          //虚拟头结点 也是新链表的头结点
          let dummyHead = ListNode()
          var lastNode = dummyHead

          //改为可变链表后面需要遍历
          var p1 = l1
          var p2 = l2

          //进位值
          var carry = 0
          //只要有个链表不为空都需要相加，另外一个可以当做是0
          while p1 != nil || p2 != nil {
              var v1 = 0
              if p1 != nil {
                  v1 = p1?.val ?? 0 //先取出来，如果是空默认值为0
                  p1 = p1?.next //p1后移
              }

              var v2 = 0
              if l2 != nil {
                  v2 = p2?.val ?? 0 //先取出来，如果是空默认值为0
                  p2 = p2?.next //p2后移
              }

              let sum = v1 + v2 + carry
              //设置进位值
              carry = sum / 10
              //sum的个位数作为新节点的值
              lastNode.next = ListNode(sum % 10)
              lastNode =  lastNode.next!
          }
          //处理最后的进位
          if carry > 0 {
              // carry == 1
              lastNode.next = ListNode(carry)
          }

          return dummyHead.next
}

解题思路：

这里还是使用虚拟节点，每次去取两个链表的值相加的时候都需要再把进位值算进去，由于每次只能把sum的个位数作为新节点的值，所以进位的值只能留给后面的sum相加，获取新的值都插入到lastNode尾部，最后还需要处理剩下的进位值，这里如果有进位值只会是1
注意点：
遍历的结束条件是两方都没有值了才结束，也就是说都为 nil
一方链表为nil，就当做是 0

3.相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

func getIntersectionNode(_ headA: ListNode?, _ headB: ListNode?) -> ListNode? {
            guard headA != nil else {return nil}
            guard headB != nil else {return nil}

            //改为可变链表方便遍历
            var pA: ListNode? = headA
            var pB: ListNode? = headB

            //相交链表代表地址是一样的，同一个对象，不需要去比较值
            //swift中==是判断实例相等，===是地址相等 这里是比较地址所以需要用到!==
            while pA !== pB  {
                 pA = pA == nil ? headB : pA?.next
                 pB = pB == nil ? headA : pB?.next
            }
            //能执行到这里代表找到相交的节点了
            return pA
    }

解题思路：

题目让我们找到相交节点，代表需要找到两个链表同一个对象，也就是同一个地址，但是我们需要考虑到两个链表长度是不一定一样长的，所以我们需要保证两个链表一样长，我们可以把两个链表头都保留起来，每次一方为nil就拼接另外一条链表进行遍历，这样子就能保证两条链表同时next遍历了，只要找到就跳出循环，返回pA节点。

参考如下图所示：
绿色代表不相交，红色代表相交

4.分隔链表

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你应当 保留 两个分区中每个节点的初始相对位置。

示例

输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]

提示

• 链表中节点的数目在范围 [0, 200] 内
• -100 <= Node.val <= 100
• -200 <= x <= 200

func partition(_ head: ListNode?, _ x: Int) -> ListNode? {
              guard head != nil else {return nil}
              //遍历链表指针
              var pHead = head

              //虚拟头结点 l
              let lHead = ListNode()
              //虚拟尾结点 l
              var lTail =  lHead

              //虚拟头结点 r
              let rHead = ListNode()
              //虚拟尾结点 r
              var rTail =  rHead

              while pHead != nil {
                  let v = pHead?.val ?? 0
                  if  v < x { //放在l
                      lTail.next = pHead
                      lTail = pHead!
                  }else{//放在r
                      rTail.next = pHead
                      rTail = pHead!
                  }
                  pHead = pHead?.next
              }

              //原链表倒数第N个节点P的值是>=x的，P后面所有节点的值都是<x的，然后rTail.next最终其实是P.
              rTail.next = nil
              //这里再把两个链表拼接起来
              lTail.next = rHead.next

              return lHead.next
}

解题思路:

使用两个虚拟节点L和R，L放小于x的节点,R放大于等于x的节点,最后把两个链表拼接起来，这里需要注意的是，rTail需要把next置空，不然可能导致后面的节点都是小于x节点的。

5. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表

示例

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

func reverseList(_ head: ListNode?) -> ListNode? {
        var p =  head
        var newHead:ListNode? =  nil
        while p != nil{
            let temp = p?.next //先暂时保存当前节点的下一个节点，用来往后遍历
            p?.next =  newHead //p 的下一个节点指向新的链表的最前端
            newHead = p //p 连接到新的链表上
            p = temp //往后移
        }
        return newHead
    }

解题思路：

新建一条链表，遍历原来的链表，每次把当前结点的next指向新链表，再把当前结点放到新链表头结点，一直往后遍历直到next为nil，反转完成。

6.回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例

输入：head = [1,2,2,1]
输出：true

回文的意思就是左边念数字和右边念数字是一样的，也就是左右对称的

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func isPalindrome(_ head: ListNode?) -> Bool {
            //这里处理空节点和1个节点
            if head == nil || head?.next == nil {return true}
            //这里处理只有2个节点
            guard head?.next?.next != nil  else {return head?.val == head?.next?.val}

            //能到这里最少有3个节点
            //找到中间节点
            var mid = middleNode(head)

            //翻转右半部分（中间节点的右边部分）
            var rHead = reverseList(mid?.next)
            var lHead = head
            var rOldHead = rHead

            // 从lHead、rHead出发，判断是否为回文链表
            var result = true
            while rHead != nil {
                if lHead?.val != rHead?.val {
                    result =  false
                    break
                }
                rHead = rHead?.next
                lHead = lHead?.next
            }
            // 恢复右半部分（对右半部分再次翻转）这里可以不写也能通过，不过这样子能不破坏原来的链表结构
            reverseList(rOldHead)
            return result  
    }
    
    /**
     * 用快慢指针查找中间节点（右半部分链表头结点的前一个节点）
     * 比如 1>2>3>2>1中的3是中间节点
     * 比如 1>2>2>1中左边第一个2是中间节点
     * @param head
     * @return
     */
    func middleNode(_ head:ListNode?) -> ListNode?{
            var fast = head
            var slow = head
            while fast?.next != nil && fast?.next?.next != nil {
                slow = slow?.next
                fast = fast?.next?.next
            }
            //返回慢指针节点就是中间节点
            return slow
    }

   /**
	 * 翻转链表
	 * @param head 原链表的头结点
	 * 比如原链表：1>2>3>4>null，翻转之后是：4>3>2>1>null
	 * @return 翻转之后链表的头结点（返回4）
	 */
    func reverseList(_ head: ListNode?) -> ListNode? {
        var p = head
        var newHead:ListNode? = nil
        while p != nil {
            let temp = p?.next
            p?.next = newHead
            newHead = p
            p = temp
        }
        return newHead
    }
}

解题思路：

这里用到两个链表知识点，第一个是用快慢指针查找中间节点查找单链表的中间节点，第二个是反转单链表，只要找到中间节点之后的节点进行反转，之后遍历两个节点，都相同就是回文链表，如果想不破坏原来的链表结构，需要在结尾把反转的链表再反转回来足矣。

7.删除链表中的节点

请编写一个函数，用于 删除单链表中某个特定节点 。在设计函数时需要注意，你无法访问链表的头节点 head ，只能直接访问 要被删除的节点 。

题目数据保证需要删除的节点 不是末尾节点 。

示例

输入：head = [4,5,1,9], node = 5
输出：[4,1,9]
解释：指定链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9

提示

链表中节点的数目范围是 [2, 1000]
-1000 <= Node.val <= 1000
链表中每个节点的值都是唯一的
需要删除的节点 node 是 链表中的一个有效节点 ，且 不是末尾节点

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.next = nil
 *     }
 * }
 */

class Solution {
    func deleteNode(_ node: ListNode?) {
        node?.val = node?.next?.val ?? 0
        node?.next = node?.next?.next   
    }
}

解题思路：

一般删除节点需要知道上一节点，把上一节点的next指向要删除节点的next足矣，但是这里题目只给到我们删除的节点，没法获取上一节点，那怎么办呢？
其实只要把下一个节点的值赋给当前节点值,这样子删除当前节点或者删除当前节点next节点都是一样的，[4,1,1,9],
所以我们就删除下个节点足矣。

8.环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。 否则，返回 false 。

示例

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

提示

• 链表中节点的数目范围是 [0, 104]
• -105 <= Node.val <= 105
• pos 为 -1 或者链表中的一个 有效索引 。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.next = nil
 *     }
 * }
 */

class Solution {
    func hasCycle(_ head: ListNode?) -> Bool {
        guard head != nil else {return false}
        guard head?.next != nil else {return false}
        
        var slow = head
        var fast = head?.next
        while fast != nil {
            if slow === fast {return true}
            slow = slow?.next
            fast = fast?.next?.next
        }

        return false

    }
}

解题思路：

我们利用快慢指针，慢指针每次遍历只位移一次，快指针位移两次，只要有环，它们肯定会相遇，类似我们在操场跑道跑步一样，跑得快的同学，迟早会跟跑得慢的同学相遇。

9.合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

提示

• 两个链表的节点数目范围是 [0, 50]
• -100 <= Node.val <= 100
• l1 和 l2 均按 非递减顺序 排列

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func mergeTwoLists(_ list1: ListNode?, _ list2: ListNode?) -> ListNode? {
            guard list1 != nil else {return list2}
            guard list2 != nil else {return list1}

            var l1 = list1 
            var l2 = list2 
            let dummyHead = ListNode()
            var dummyTail = dummyHead //末尾节点，用来添加新的节点
            while l1 != nil && l2 != nil {
                let v1 =  l1?.val ?? 0
                let v2 =  l2?.val ?? 0
                if v1 < v2 {
                    dummyTail.next = ListNode(v1)
                    l1 = l1?.next
                }else{
                    dummyTail.next = ListNode(v2)
                    l2 = l2?.next
                }
                dummyTail = dummyTail.next!
            }
     
            dummyTail.next = l1 == nil ? l2 : l1 //可能两个链表长度不一样，所以最后一个节点也要添加上去

            return dummyHead.next
    }
}

解题思路：

我们可以使用两个指针去遍历两个有序链表，有序这个是个关键点，每次拿到两个链表的节点依次比较添加，最后的链表肯定是有序的。
第一步：
每次遍历都判断两个指针的节点大小，添加进去的节点都需要位移，dummyTail 也要位移，最后只要有一个链表节点为nil,代表第一步合并结束，
第二步：
还需要处理一个问题，可能两个链表长度不一样，所以最后一个节点也需要添加上去。

10.合并K个升序链表

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

提示：

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按 升序 排列
lists[i].length 的总和不超过 10^4

func mergeKLists(_ lists: [ListNode?]) -> ListNode? {
        guard lists.count != 0 else{return nil}
        var dummy:ListNode?
        for node in lists {
            dummy = mergeTwoLists(dummy,node)
        }

        return dummy
    }

    func mergeTwoLists(_ list1: ListNode?, _ list2: ListNode?) -> ListNode? {
            guard list1 != nil else {return list2}
            guard list2 != nil else {return list1}

            var l1 = list1 
            var l2 = list2 
            let dummyHead = ListNode()
            var dummyTail = dummyHead //末尾节点，用来添加新的节点
            while l1 != nil && l2 != nil {
                let v1 =  l1?.val ?? 0
                let v2 =  l2?.val ?? 0
                if v1 < v2 {
                    dummyTail.next = ListNode(v1)
                    l1 = l1?.next
                }else{
                    dummyTail.next = ListNode(v2)
                    l2 = l2?.next
                }
                dummyTail = dummyTail.next!
            }
     
            dummyTail.next = l1 == nil ? l2 : l1 //可能两个链表长度不一样，所以最后一个节点也要添加上去

            return dummyHead.next
    }

第一个解题思路：(数据多的时候容易超时)

采用合并两个有序链表方法来解答，只需要在外面遍历整个数组即可。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    // 分治思想
    func mergeKLists(_ lists: [ListNode?]) -> ListNode? {
    
      if lists.count == 0 {
        return nil
      }
      //重点！ 一直分治下去迟早只有一个，直接返回改元素
      if lists.count == 1 {
        return lists[0]
      }
    
      let mid = lists.count/2
    	//假设函数已经完成递归分成两份
      let left = mergeKLists(Array(lists[0..<mid]))
      let right = mergeKLists(Array(lists[mid..<lists.count]))
    
      return mergeTwoLists(left, right)
    }

    func mergeTwoLists(_ list1: ListNode?, _ list2: ListNode?) -> ListNode? {
            guard list1 != nil else {return list2}
            guard list2 != nil else {return list1}

            var l1 = list1 
            var l2 = list2 
            let dummyHead = ListNode()
            var dummyTail = dummyHead //末尾节点，用来添加新的节点
            while l1 != nil && l2 != nil {
                let v1 =  l1?.val ?? 0
                let v2 =  l2?.val ?? 0
                if v1 < v2 {
                    dummyTail.next = ListNode(v1)
                    l1 = l1?.next
                }else{
                    dummyTail.next = ListNode(v2)
                    l2 = l2?.next
                }
                dummyTail = dummyTail.next!
            }
     
            dummyTail.next = l1 == nil ? l2 : l1 //可能两个链表长度不一样，所以最后一个节点也要添加上去

            return dummyHead.next
    }
}

第二种解题思路：分治思想 （优）

基于前面的代码，我们应该对大问题进行分解，所以我们想到了分治思想。
分治思想就是把一个复杂的问题分成两个或更多的相同或 相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解。
我们假设 mergeKLists 函数已经实现，那么我们就可以对原数组进行分治，分开两边去处理，得到两个链表，然后我们对这两个链表进行合并即可。需要注意的是我们代码 Array(lists[0..<mid]) 需要让 mid > 0。 所以递归分治下去，数组迟早只有一份，我们返回一份即可，最终合并的时候都只会是两个链表进行合并，达到用需要解决的问题来解决自己本身，是不是很有code魅力！