力扣T206：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

分析：这是一道比较简单的题目，但是了解它的思想比做这道题本身更重要。

可以分为递归和迭代两种做法。迭代法比较常规而且节省内存，但使用对这道题递归可以让我们学会递归的思维模式。

迭代法思路需要用到p1/p2/p3共3个指针。

func reverseList(head *ListNode) *ListNode {
	if head == nil || head.Next == nil{
		return head
	}
	p1, p2 := head, head.Next
	for p2 != nil{
		p3 := p2.Next
		p2.Next = p1
		p1 = p2
		p2 = p3
	}
	head.Next = nil
	return p1
}

 

假设有A->B->C->D->E五个节点，反转函数为reverseList。递归思路就是：reverseList(A~E)等价于A.Next=nil再把reverseList(B~E)的最后一个节点指向A：

func reverseList0(head *ListNode) *ListNode {
	if head == nil || head.Next== nil{
		return head
	}

	newHead := reverseList0(head.Next)
	head.Next.Next = head
	head.Next = nil
	return newHead
}

 

 

力扣T92: 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

分析：只需要先用一个指针遍历到left节点之后，再让p1和p2分别指向left和left.next往后遍历并交换（和上一题一样的行为），直到边界right为止。

func reverseBetween(head *ListNode, left int, right int) *ListNode {
	if left == right{
		return head
	}

	dummy := &ListNode{}
	dummy.Next = head
	p1 := dummy
	for i:=0; i<left-1; i++{
		p1 = p1.Next
	}
	conn1 := p1
	p1 = p1.Next
	p2 := p1.Next
	p3 := p2
	for i := 1; i<=right-left; i++{
		p3=p2.Next
		p2.Next = p1
		p1 = p2
		p2 = p3
	}

	conn1.Next.Next = p3
	conn1.Next = p1
	return dummy.Next
}

 

 

力扣T25：K 个一组翻转链表

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

已给出函数签名：

func ReverseKGroup(head *ListNode, k int) *ListNode

 

按递归的思想，ReverseKGroup(head, k)就相当于把前k个节点逆转之后再对第k+1个节点调用ReverseKGroup(headK, k)。

func reverseKGroup(head *ListNode, k int) *ListNode {
	if head == nil{
		return nil
	}
	newHead, tail, nextGroup, succ := reverseKNode(head, k)
	if !succ{
		reverseKNode(newHead, k)
		return tail
	}
	if nextGroup == nil{
		return newHead
	}
	tail.Next = reverseKGroup(nextGroup, k)
	return newHead
}

func reverseKNode(head *ListNode, k int) (*ListNode, *ListNode, *ListNode, bool){
	t := k-1
	if head == nil || head.Next == nil{
		return head,head,nil, true
	}
	p1, p2 := head, head.Next
	for i:=1; i<k; i++{
		if p2 == nil{
			break
		}
		p3 := p2.Next
		p2.Next = p1
		p1 = p2
		p2 = p3
		t--
	}
	head.Next = nil
	return p1, head, p2, t == 0
}

 

 

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

要求用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题。

分析：用快慢指针找到中间节点，再反转中间节点后的那一半节点，然后就可以在用新的双指针从链表两端往中间遍历比对：

func reverseList(head *ListNode) *ListNode {
    var prev, cur *ListNode = nil, head
    for cur != nil {
        nextTmp := cur.Next
        cur.Next = prev
        prev = cur
        cur = nextTmp
    }
    return prev
}

func endOfFirstHalf(head *ListNode) *ListNode {
    fast := head
    slow := head
    for fast.Next != nil && fast.Next.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
    }
    return slow
}

func isPalindrome(head *ListNode) bool {
    if head == nil {
        return true
    }

    // 找到前半部分链表的尾节点并反转后半部分链表
    firstHalfEnd := endOfFirstHalf(head)
    secondHalfStart := reverseList(firstHalfEnd.Next)

    // 判断是否回文
    p1 := head
    p2 := secondHalfStart
    result := true
    for result && p2 != nil {
        if p1.Val != p2.Val {
            result = false
        }
        p1 = p1.Next
        p2 = p2.Next
    }

    // 还原链表并返回结果
    firstHalfEnd.Next = reverseList(secondHalfStart)
    return result
}

 

 

下面是递归法，时间复杂度和空间复杂度都是O(n)：

func isPalindrome(head *ListNode) bool {
	p1,  res := head, true
	var iterList func (h *ListNode)
	iterList = func(h *ListNode){
		if h == nil{
			return
		}
		iterList(h)
		if h != p1{
			res = false
			return
		}
	}
	return res
}