【269期】链表高频面试题（包括反转、合并、相交、分割、环长等）

1.整个链表翻转

https://leetcode-cn.com/problems/reverse-linked-list/

1.1 题目描述

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

1.2 算法实现

1.2.1 算法思路

双指针：一个指针pre指向原链表当前节点的前一个节点，另一个指针next暂存当前节点的下一个节点。

依次遍历链表的各个节点，每遍历一个节点即将其指向前一个节点（倒置），主要分4步：

先备份后一个节点（以防移动指针的时候找不到下一个节点）：next = head.Next；
后一个节点的Next指向前一个节点：next.Next = pre；
前置节点后移一个位置到当前节点：pre = head;
后置节点后移一个位置到下一个节点：head = next，注意这一步（千万不要）容易忽略。

1.2.2 代码实现

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func partition(head *ListNode, x int) *ListNode {
    //var preHead, postHead *ListNode     // 前后两部分链表的头结点，不能这么声明，这样声明的话两者都为&ListNode{0, nil}其中Next域为nil，当运行到prePtr.Next = head时会报panic: runtime error:invalid memory address or nil pointer deference错误
    preHead := &ListNode{0, nil}        // 生成一个preHead链表的头结点，该节点固定一直不对其移动，改头节点的Val为多少都不影响结果，因为使用的是头结点的Next节点
    postHead := &ListNode{0, nil}       // 生成一个postHead链表的头结点，该节点固定不动
    prePtr := preHead                   // prePtr指针对preHead链表进行遍历，注意：开始时其指向preHead
    postPtr := postHead
    for head != nil {                   // 遍历原链表
        if(head.Val < x ){              // 小于x的节点尾插到preHead链表后面
            prePtr.Next = head          // prePtr的Next域指向当前节点，即将当前节点从preHead链表尾部prePtr依次插入
            prePtr = head               // prePtr指针后移一位，指向当前节点
        }else{                          // 大于等于x的节点放在postHead链表的后面
            postPtr.Next = head         // 将当前节点插入到postHead链表尾节点postPtr后面
            postPtr = head              // postHead链表的尾节点后移一位
        }
        head = head.Next                // 当前指针后移一位
    }
    // 对head链表遍历结束分为preHead和postHead两个子链表
    prePtr.Next = postHead.Next         // 注意：这里是将preHead链表的尾节点prePtr的Next域指向postHead链表头结点的下一个节点
    postPtr.Next = nil                  // postPtr的尾节点的Next域指向空
    return preHead.Next                 // 返回preHead链表的Next之后的链表
}