翻转链表

• 第一反应，使用栈结构翻转

翻转操作第一直觉就是用栈
将需要翻转的链表结点依次入栈，然后依次出栈，理顺next指针的关系，很方便就翻转好了
空间复杂度O(n)

• 三步登基法 循环修改指针

其实修改指针的过程和古代太子继位的过程是一样一样的，翻转链表的全过程也非常类似一个朝代所有帝王更迭的过程
怎么用太子继位的过程来理解每一次翻转的过程呢？

敲黑板！三步登基法：太子继位 + 新定太子 + 登基大典

需要用到三个指针：

new_head：新皇指针，指向新头的指针
origin_head(也就是head，最初的链表头指针，永远指向最初的链表头结点，忠诚如宰相)：宰相指针，origin_head.next指定太子结点（下一个头节点）
now_head: 当朝皇指针，指向当前的头结点

• step A 太子继位

将太子结点（origin_head的next结点）作为new_head
new_head = origin_head.next

• step B 宰相新定太子

新定太子人选--修改origin_head.next，让它指向new_head的next（把太子的儿子定为新太子）
origin_head.next = new_head.next

• step C 举行登基大典

太子登基，变成新头。修改new_head.next，指向now_head
new_head.next = now_head
向世人宣告，将now_head指向new_head
now_head = new_head

具体过程如图所示

通过修改指针翻转链表示意图

理解了三步登基法，写成代码就水到渠成了：

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

class Solution:
    def reverseGroup(self, head: ListNode) -> ListNode:
        # 如果链表为空，直接返回
        if head == None:
            return head
        now_head = head
        # 循环，三步登基法
        while head.next:
            new_head = head.next
            head.next = new_head.next
            new_head.next = now_head
            now_head = new_head
        return now_head

进阶-以组(team)为单位，翻转链表

将链表的若干个结点视为一组(team)，可以进行组外翻转和组内翻转
而对一个链表做组外翻转+组内翻转，等于将链表翻转一次

• 组外翻转

假设以4个结点为一组，链表[1,2,3,4,5,6,7,8,9,10,11]从head开始进行组外翻转，得到目标链表[9,10,11,5,6,7,8,1,2,3,4]

如果将一组结点看成一个大结点，那么组外翻转也可以类比单结点三步登基法翻转

基于单结点三步登基法，组三步登基法有一点点不同
对于组而言，太子由team_head组的尾结点head_end的next来指定，太子登基时也需要把太子组的尾结点new_head_end的next指向当前的头结点（当朝皇结点），具体可以看下面的过程：

• step A 太子继位

将太子组的头结点（team_head尾结点head_end的next结点）作为new_head
new_head = head_end.next

• step B 宰相新定太子

新定太子人选--修改head_end.next，让它指向team_new_head的尾结点new_head_end.next（把太子的儿子定为新太子）
head_end.next = new_head_end.next

• step C 举行登基大典

太子登基，变成新头。修改new_head.next，指向now_head
new_head.next = now_head
向世人宣告，将now_head指向new_head
now_head = new_head

以k个结点为一组，实现组外翻转的代码如下：

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

class Solution:
    def reverseGroupOutTeam(self, head: ListNode, k: int) -> ListNode:
        # 如果链表为空，直接返回
        if head == None:
            return head
        head_end = head
        # 将 head_end 指向 team_head 的尾部
        # 定位head_end指针的位置。 如果一开始 team_head 长度不足k，不用翻转直接返回
        for i in range(k-1):
            head_end = head_end.next
            if head_end == None:
                return head
        # 初始化now_head/now_head_end/new_head/new_head_end
        now_head = head
        new_head = head
        now_head_end = head_end
        new_head_end = head_end
        # 循环，三步登基法
        # 当存在太子的时候
        while head_end.next:
            # 太子继位
            new_head = head_end.next
            # 定位太子组的尾结点指针的位置，定位成功后结束for循环
            new_head_end = new_head
            for i in range(k-1):
                if new_head_end.next:
                    new_head_end = new_head_end.next
                else:
                    break
            # 宰相指定新太子
            head_end.next = new_head_end.next
            # 太子登基
            new_head_end.next = now_head
            now_head = new_head
        return now_head

• 组内翻转

仍然假设以4个结点为一组，链表[1,2,3,4,5,6,7,8,9,10,11]从head开始进行组内翻转，不足4个结点的组不需要组内翻转保持原样，得到目标链表[4,3,2,1,8,7,6,5,9,10,11]

容易发现，组内翻转整个链表 = 翻转第一组 + 组内翻转剩余链表，这显然可以写成一个递归的过程。那么基本的思路就是，使用三步登基法翻转当前链表的第一组结点，然后调用自身对剩余链表进行组内翻转

比如下面这一题，就是原滋原味的组内翻转：

给定一个链表，每 k 个节点一组进行翻转
k 是一个正整数，它的值小于或等于链表的长度
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序
示例 :
给定链表：1->2->3->4->5
当 k = 2 时，返回: 2->1->4->3->5
当 k = 3 时，返回: 3->2->1->4->5

思路：
A) 组内翻转整个链表 = 翻转第一组 + 组内翻转剩余链表
B) 由于不足k个的那一组不用翻转，所以需要额外增加一个检察官指针check_head检查当前的第一组是否足有k个结点。足够则翻转，不足则不翻转，直接返回

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

class Solution:
    def reverseGroupInTeam(self, head: ListNode, k: int) -> ListNode:
        # 总体思路：以k个结点为一组，翻转第一组+递归
        
        # 如果链表为空，直接返回
        if head == None:
            return head
        # 初始化宰相指针和当朝皇指针,并初始化一个检察官指针check_head，测试当前组是否足够k个结点
        new_head = head
        now_head = head
        check_head = head
        for i in range(k-1):
            check_head = check_head.next
            if check_head == None:
                break
        # 如果当前第一组足够k个结点
        if check_head:
            for i in range(k-1):
                new_head = head.next
                if i == (k-2):
                    head.next = self.reverseGroupInTeam(new_head.next, k)
                else:
                    head.next = new_head.next
                new_head.next = now_head
                now_head = new_head
        return now_head

如果在上面这题的基础上变一下，把从链表头开始组队改成从链表尾部开始组队，其余条件不变
示例 :
给定链表：1->2->3->4->5
当 k = 2 时，返回: 1->3->2->5->4
当 k = 3 时，返回: 1->2->5->4->3

思路1：先派一个检查官指针check_head遍历链表结点，记录结点总数，计算第一组由几个结点组成，然后剩余结点的组内翻转就转换成了上一题从链表头开始组队进行组内翻转的问题

def reverseKGroup(self, head: ListNode, k: int) -> ListNode:        
        # 如果链表为空，直接返回
        if head == None:
            return head
        # 初始化一个试探指针check_head
        check_head = head
        count = 1
        while check_head.next:            
            check_head = check_head.next
            count += 1
        # 如果结点总数是k的倍数，直接做组内翻转
        if count % k == 0:
            return self.reverseGroupInTeam(head, k)
        # 如果结点总数不是k的倍数，保持第一组不动，对剩余结点做组内翻转
        else:
            first_team_end = head
            for i in range(count % k - 1):
                first_team_end = first_team_end.next
            # 对剩余结点做组内翻转
            first_team_end.next = self.reverseGroupInTeam(first_team_end.next, k)
            return head

思路2：先将链表翻转一次，然后从新的链表头开始进行组外翻转。如果最后一组不足k个结点，再对最后一组进行一次翻转。即1->2->3->4->5变成5->4->3->2->1，再变成1->3->2->5->4
代码不贴了

人生金道理：

从思路1和思路2可以看到，组内翻转和组外翻转是对链表进行各种奇葩翻转的基本工具，它们的互相配合往往可以实现一些复杂的链表翻转

使用链表翻转，在O(N)时间复杂度和O(1)空间复杂度下解决【回文链表检测问题】
思路：
【V型相交链表法】

• 1.使用快慢指针找到链表中点（注意链表奇偶长度下中点位置的讨论，在我的代码中，偶数长度的链表中点会右偏，奇数长度的就刚好是中点）
• 2.翻转后半部分链表，让整个链表变成V型的双头同尾的相交链表
• 3.从两个头出发，同步依次比较
  这是leetcode #### 234. 回文链表

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        if not head:
            return True

        # 找到中间节点，翻转后一半链表
        slow = fast = head
        # 奇数长度slow来到中间，偶数长度slow右偏
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        # 偶数长度
        if fast is None:
            # 加一个节点，让链表变成奇数长度，slow变成正中结点，转为奇数长度链表处理
            n = ListNode(slow.val)
            n.next = slow.next
            slow.next = n
        # 奇数长度
        head1 = self.reverse(slow)
        while head and head1 and head1.val == head.val:
            head = head.next
            head1 = head1.next
        if head:
            return False
        return True

    def reverse(self, head):
        if not head:
            return
        cur = head
        while head.next:
            new_head = head.next
            head.next = new_head.next
            new_head.next = cur
            cur = new_head
        return cur