7.14反转链表 - WisperDin/blog GitHub Wiki

7.14 反转链表

题目

定义一个函数，输入链表头结点，反转该链表并输出反转后的链表头结点

难点

对链表操作的方向与链表方向相反，即遍历到后面的节点时需要对前面的节点进行操作，对于这类问题，可以考虑多指针的方法

思路

分析每次操作影响到的节点(工作区)，定义多个指针，每趟操作后集体移动

graph LR
A-->B
B-->C
C-->D
Loading

要使这个链表反转，需要记录A,B 指针，使得B.next 指向 A,但是如果修改的B.next 之后，B原来的next C 就没办法访问到(断裂)，所以需要记录A,B,C指针的位置

修改后

PTR:   P1  P2  P3 
NODE:  A<--B   C-->D

此时继续下一趟遍历

PTR:       P1  P2  P3 
NODE:  A<--B   C-->D

修改后

PTR:       P1  P2  P3 
NODE:  A<--B<--C-->D

当到达P3尽头时，意味着将是最后一趟

PTR:           P1  P2
NODE:  A<--B<--C-->D

修改后

PTR:           P1  P2
NODE:  A<--B<--C<--D

所以分析得，工作区有三个节点，在最后一趟中为两个

实现代码

package reverseList

type Node struct {
	Val int
	Next *Node
}

func ReverseList(list *Node) *Node {
	if list == nil {
		return nil
	}
	cur := list
	//only one node
	if cur.Next == nil {
		return cur
	}
	curN := cur.Next
	cur.Next = nil

	for curN != nil{
		//record cur next next
		curNN := curN.Next
		//reverse ptr
		curN.Next = cur
		if curNN == nil{
			return curN
		}
		cur = curN
		curN = curNN
	}
	return nil
}

扩展 -- 递归实现

思路：

通过递归往后遍历链表到末尾时，

返回尾节点

返回到上一层非尾节点时，执行使链表反转的操作，继续将尾节点往上返回，

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
	if head == nil {
		return nil
	}
	if head.Next == nil {
		return head
	}
	return recList(head)
}

func recList(head *ListNode) *ListNode{
	if head.Next==nil{
		return head
	}
	newHead := recList(head.Next)
	//reverse
	if head.Next.Next==nil{
		//arrive the last 2 pos (right order)
		head.Next.Next = head
		head.Next = nil
	}
	return newHead
}
⚠️ **GitHub.com Fallback** ⚠️