反转链表

链表这部分最常见的就是链表反转，这里主要针对三种题型来对链表的反转问题进行了讲解。分别对应leetcode中的题目如下：
反转一个单链表
两两交换链表中的节点
每 k 个节点一组翻转链表
每个问题难度循序渐渐，以下算法通过scala语言实现

• 首先定义数据结构：ListNode

class ListNode(var _x: Int = 0){
  var next: ListNode = _
  var x: Int = _x
}

数据结构的定义决定了你的算法实现，数据结构也是一个很容易忽略的问题。

反转一个单链表

算法思路如下：因为要将节点的指针反转，也就是当前节点的next指针由原来的指向后续节点变为指向前序节点，那么我们这里需要三个变量：cur、pre、next分别来指向当前节点，当前节点的前节点，当前节点的后节点。因为我们后面要改变cur.next的值，为了防止原始指针丢失，用next指针来保存，next = cur.next, 因为需要将cur.next指向前序节点，那么这里用pre保存前序节点的指针，然后另cur.next = pre就好了。

这里的指针只是变动了一次，由后续节点变为了前序节点。
具体实现如下：

  def swapNodes(head: ListNode): ListNode = {
    if(head == null){
      return head
    }

    //pre does not need to initialize
    var pre: ListNode = null
    var cur = head
    var next: ListNode = null
    while(cur.next != null){
      next = cur.next
      cur.next = pre
      pre = cur
      cur = next
    }
    cur.next = pre
    cur
  }

两两交换链表中的节点

算法思路如下：跟简单的反转链表相比，这里做了限定，只是两两节点的指针反转。这里使用两个变量分别保存需要反转的节点的前序节点（pre）和需要反转的节点的后续节点（post）。然后当pre.next != null && pre.next.next != null时进行指针的变动。变动之后在更新pre和post在继续变动。

这里指针需要变动三次：

pre.next.next.next = pre.next
pre.next = pre.next.next
pre.next.next.next = post

具体实现如下：

def swapInPairs(head: ListNode): ListNode = {
    val dummy: ListNode = new ListNode(-1)
    var pre = dummy
    dummy.next = head
    var post: ListNode = null
    while (pre.next != null && pre.next.next != null){
      post = pre.next.next.next
      pre.next.next.next = pre.next
      pre.next = pre.next.next
      pre.next.next.next = post
      pre = pre.next.next
    }

    dummy.next
  }

因为两两交换的时候头结点会改变，这里在头节点前面加一个虚拟节点dummy，让dummy .next = head，后面随便的变换，我们只要保证后面dummy.next一直指向改变后的头结点就好，最后返回dummy.next就好。这里pre = dummy， pre.next = pre.next.next保证了dummy.next一直指向改变后的头结点。

每 k 个节点一组翻转链表

这里跟两两节点反转的不同是由原来的2变成了k，因为k不确定，所以不能简单的通过一个循环来判断并变换。
我们通过一个函数来交换需要交换的k个节点，然后每次向后取k个节点将其传入该函数进行变换，另一个函数来取k个节点。
交换函数需要传入两个指针，一个是k个节点的前节点(pre)，一个是k个节点的后节点(post),返回值是交换后的pre节点。

-1->1->2->3->4->5
 |           |
pre         next

-1->3->2->1->4->5
          |  |
         pre next

只要next走过k个节点，就可以调用翻转函数来进行局部翻转了
代码实现如下：

  def swapInKNodes(head: ListNode, k: Int): ListNode = {
    if(head == null){
      return head
    }

    var count: Int = 0
    val dummy = new ListNode(-1)
    dummy.next = head
    var pre = dummy
    var post: ListNode = head
    while(post.next != null){
      count = count + 1
      post = post.next

      if(count % k == 0){
        pre = swapKNodes(pre, post)
        println("pre: "+ pre.x)
      }
    }

    dummy.next
  }

  def swapKNodes(pre: ListNode, post: ListNode): ListNode = {

    val head = pre.next
    var last = pre.next
    var next : ListNode = null
    var cur = last.next
    while(cur != post){
      next = cur.next
      cur.next = last
      last = cur
      cur = next
    }
    head.next = post
    pre.next = last

    head
  }

参考如下：Reverse Nodes in k-Group 每k个一组翻转链表