在链表的第n个位置插入一个节点

This is a hackerrank problem "to insert a node in the nth position of a linked list". From the problem's description, we are supposed to insert 10 at position 1.

这是一个“将节点插入链表的第n个位置”的黑客问题。从问题的描述中,我们应该在位置1插入10。

3 > 5 > 4 > 2 > Null is an existing linked list and we have to insert 10 at index one. The output should look like this 3 >10 > 5 > 4 > 2 > Null. This is my code:

3> 5> 4> 2> Null是一个现有的链表,我们必须在索引1处插入10。输出应该看起来像3> 10> 5> 4> 2> Null。这是我的代码:

def InsertNth(head, data, position):
    temp = Node(data)
    if (head == None):
        head = temp  #if head is Null then new node is the head
        temp.next = None
        #return head
    else:
        current = head
        i = 0
        while(i < position - 1):
        #for i in range(position-1):
            current = current.next 
            i = i +1
        next_node = current.next  #keep the address to the next element
        current.next = temp .     
        temp.next = next_node
    return head

The output I get using this code is 2> 10 > 5 > 4 > 2 > Null, which is wrong. I tried a lot to fix, but the code looks fine to me. Can anyone please point out my error, with some explanation ?

我使用此代码得到的输出是2> 10> 5> 4> 2> Null,这是错误的。我尝试了很多修复,但代码看起来很好。任何人都可以指出我的错误,有一些解释?

1 个解决方案

#1

Here's how I'd do it. You need two checks in your while - one to make sure i does not cross position, and the other is to ensure that you do not fall off the end of the linked list (possible when position is greater than the size of your linked list).

我就是这样做的。你需要两次检查 - 一次是为了确保我没有交叉位置,另一种是为了确保你不会脱离链表的末尾(当位置大于链表的大小时可能) 。

If you are to insert at position, i should stop at position - 1. Then, set cur.next to be temp, and temp.next to be cur.next's old value. You do not need a surrogate object for swapping pointers (next_node, in your code is unnecessary).

如果要插入位置,我应该停在位置 - 1.然后,将cur.next设置为temp,将temp.next设置为cur.next的旧值。您不需要代理对象来交换指针(next_node,在您的代码中是不必要的)。

def insert(head, data, position):
    temp = Node(data)
    # handle all the base cases - empty list or position == 0
    if not head or position == 0:
        temp.next = head
        head = temp
    else:       
        cur = head
        i = 0
        while i < position - 1 and cur.next is not None:   
            cur = cur.next
            i += 1
        temp.next = cur.next
        cur.next = temp

    return head

Follow PEP8 standards please, snake case for identifier names only.

请遵循PEP8标准,仅用于标识符名称的蛇形案例。

_{Challenge can be found at https://www.hackerrank.com/challenges/insert-a-node-at-a-specific-position-in-a-linked-list/problem}.

可以在https://www.hackerrank.com/challenges/insert-a-node-at-a-specific-position-in-a-linked-list/problem找到挑战。

#1