翻转链表和k个一组翻转以及两两反转

 

 一。输入一个链表，输出反转后的链表。 

非递归实现：

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        if pHead is None:
            return pHead
        last = None  #指向上一个节点
        while pHead:
            # 先用tmp保存pHead的下一个节点的信息，
            # 保证单链表不会因为失去pHead节点的next而就此断裂
            tmp = pHead.next
            # 保存完next，就可以让pHead的next指向last了
            pHead.next = last
            # 让last，pHead依次向后移动一个节点，继续下一次的指针反转
            last = pHead
            pHead = tmp
        return last

上面程序中的while循环是主要部分，主体部分代码简单，但不是很好理解，下面用图示方法，以三个链表节点为例来展示其反转过程。

1. 初始链表状态 
    需要定义一个变量last指向pHead的上一个节点

 

 2. 一次迭代之后 
     x0先暂时被从链表中脱离出来，由last指向，作为反转的新链，x0反转之后会是最后一个节点，因此next指向None，pHead则指向原链的下一个节点x1。

 

 3. 两次迭代之后 
      x1被脱离出来加入反转的新链，并插入x0之前，pHead再后移。

 

 4. 三次迭代之后 
     反转完成，pHead指向None即结束循环，返回last即为新链表的头结点。

 

 递归实现：

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        if not pHead or not pHead.next:
            return pHead
        else:
            newHead = self.ReverseList(pHead.next)
            pHead.next.next=pHead
            pHead.next=None
            return newHead

 

二。给出一个链表，每 k 个节点一组进行翻转，并返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么将最后剩余节点保持原有顺序。

示例 :

给定这个链表：1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5

当 k = 3 时，应当返回: 3->2->1->4->5

说明 :

你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

使用递归的方式：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseKGroup(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        current = head
        count = 0
        while current and count!=k:
            current = current.next
            count += 1
        if count == k:
            current = self.reverseKGroup(current,k)
            while count > 0:
                temp = head.next
                head.next = current
                current = head
                head = temp
                count -= 1
            head = current
        return head

 三。链表两两反转（递归实现）

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if head == None or head.next == None:
            return head

        l1 = head.next
        head.next = self.swapPairs(head.next.next)
        l1.next = head

        return l1

 非递归加图解

 

 

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        thead = ListNode(-1)
        thead.next = head
        c = thead
        while c.next and c.next.next:
            a, b=c.next, c.next.next
            c.next, a.next = b, b.next
            b.next = a
            c = c.next.next
        return thead.next