HackerRank问题：链表第n个位置插入节点的实现问询

这是HackerRank平台上的「在链表第n个位置插入节点」问题，具体需求是：将数值10插入到链表的位置1。现有链表为 3 > 5 > 4 > 2 > Null，插入后预期输出为 3 > 10 > 5 > 4 > 2 > Null。

先看看你提供的代码：

def InsertNth(head, data, position):
    temp = Node(data)
    if (head == None):
        head = temp  # 若head为Null，则新节点作为头节点
        temp.next = None

现有代码的问题 #

目前你的代码只处理了**链表为空（head是None）**的情况，但完全没考虑链表不为空、需要插入到指定位置（比如这里的位置1）的场景。当要插入到非0位置时，我们需要找到目标位置的前驱节点，然后调整指针完成插入。

修正后的完整代码 #

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def InsertNth(head, data, position):
    temp = Node(data)
    # 情况1：插入到链表头部（position为0，或者原链表为空）
    if position == 0 or head is None:
        temp.next = head
        return temp
    # 情况2：插入到链表中间或尾部
    current = head
    # 找到目标位置的前驱节点
    for _ in range(position - 1):
        current = current.next
    # 调整指针完成插入
    temp.next = current.next
    current.next = temp
    return head

代码解释 #

• 插入头部：如果position是0，或者原链表为空，直接让新节点的next指向原head，然后返回新节点作为新的head。
• 插入中间/尾部：遍历链表找到目标位置的前一个节点，把新节点的next指向该节点原本的next，再把该节点的next指向新节点，这样就完成了插入。

用这个代码测试你的场景：原链表是3→5→4→2，插入10到位置1，会先找到3这个前驱节点，把10的next指向5，再把3的next指向10，最终得到3→10→5→4→2，和预期一致。

内容的提问来源于stack exchange，提问作者user8261552