linked list

·

Связные списки - это одна из самых базовых структур данных, которую можно придумать в programming. Суть её заключается в том, что мы имеем узлы, в которых хранится значение, а ещё ссылки на другие элементы из списка. Списки бывают односвязные (мы знаем только следующий элемент) и двусвязные (мы знаем предыдущий и следующий элемент). Как правило, можно сделать интерпретацию массива в список и наоборот. При этом массив имеет O(1) скорость доступа к нужному элементу, а в списке O(n). Правда, список мы можем расширять сколько угодно по памяти, а массив выделяется.

struct ListNode {
    Val int
    Next *ListNode
}

Для частичных оптимизаций делают ещё одну структуру, которая позволяет держаться длину и начало/конец списка.

struct LinkedList {
   Head *ListNode
   Length int
}

Типичные операции над связными списками

Удаление элемента из односвязного списка:

element.Val = element.Next.Val
element.Next = element.Next.Next

Разворот односвязного списка:

prev = nil
current = head
for current != nil {
    next := current.Next
    current.Next = prev
    prev = current
    current = next
}

Периодически для того, чтобы найти циклы или как-то обойти быстрее по списку применяют технику двойных указателей:

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if head is None:
            return False
        slow = head
        fast = head.next
        while slow != fast:
            if fast is None or fast.next is None:
                return False
            slow = slow.next
            fast = fast.next.next
        return True

Найти k-ый элемент с конца списка:

ListNode slow, fast;
slow = fast = head;
while (k > 0) {
    fast = fast.next;
    k--;
}

while (fast != null) {
    slow = slow.next;
    fast = fast.next;
}
return slow;

Найти ноду с которой начинается пересечение двух одновязных списков. Алгоритм строиться на том, что если мы дошли до конца, то мы должны с другой ветки начать и тогда рано или поздно математика сойдётся потому они оба пройдут буть в 2*(a+b+c).

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getIntersectionNode(headA, headB *ListNode) *ListNode { 
    curA := headA
    curB := headB
    
    for curA != curB {
        if curA == nil {
            curA = headB
        } else {
            curA = curA.Next
        }
        if curB == nil {
            curB = headA
        } else {
            curB = curB.Next
        }
    }
    
    return curA
}

Удалить Nth элемент с конца:

func removeNthFromEnd(head *ListNode, n int) *ListNode {
	dummy := &ListNode{Val: 0, Next: head}
	current := dummy
    tailer := dummy
    i := -1
    
    for tailer != nil {
        tailer = tailer.Next
        if i == n {
            current = current.Next
        } else {
            i++
        }
    }
    
	current.Next = current.Next.Next
	return dummy.Next
}

It is similar to what we have learned in an array. But it can be trickier and error-prone. There are several things you should pay attention:

  1. Always examine if the node is null before you call the next field.

Getting the next node of a null node will cause the null-pointer error. For example, before we run fast = fast.next.next, we need to examine both fast and fast.next is not null.

  1. Carefully define the end conditions of your loop.

Run several examples to make sure your end conditions will not result in an endless loop. And you have to take our first tip into consideration when you define your end conditions.

Источники

Обратные ссылки