Я столкнулся с этой проблемой, решая вопросы по leetcode. Это очень хорошая проблема связанных списков. В основном проблема заключается в следующем: вам даны два связанных списка, вы должны добавить эти списки, изменив их местами, и снова отменить вывод добавления и вернуть его в виде связанного списка.. Я не буду решать эту проблему в контексте временной сложности но скорее я постараюсь упростить его до самого базового уровня. Я использую Java для решения этой проблемы. Я буду решать ее с нуля.
- 1. Сначала давайте создадим узел для связанного списка.
public class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
next = null;
}
}
- 2. Функция добавления узлов в связанный список:
public Node head = null;
public Node tail = null;
public void addNode(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
tail = newNode;
} else {
tail.next = newNode;
tail = newNode;
}
}
- 3. Функция для отображения узлов в списке.
public void display() throws IllegalStateException {
Node current = head;
if (head == null) {
throw new IllegalStateException("Your List is empty");
}
while (current != null) {
System.out.println(current.data);
current = current.next;
}
}
Верхние 3 блока кодов были обычной реализацией связанного списка и отображением их с помощью функции отображения. Сейчас, функция для обратного просмотра связанного списка:
- 4. Итеративное изменение связанного списка (вы также можете сделать это рекурсивно)
public Node reverse(Node start) throws IllegalStateException {
if (start == null) {
throw new IllegalStateException("List is empty");
}
Node current = start;
Node prev = null;
while (current != null) {
Node next = current.next;
current.next = prev;
prev = current;
current = next;
}
return prev;
}
- 5. Самый важный шаг – добавить значения из списка в строковый конструктор, преобразовать их в целое число и вернуть. Мы будем использовать это значение в основной функции. Обходной путь: Чтобы легко добавлять значения, вот почему мы делаем этот дополнительный шаг.
public static int arr(Node start) throws IllegalStateException {
Node current = start;
if (start == null) {
throw new IllegalStateException("Your List is empty");
}
StringBuilder sb = new StringBuilder();
while (current != null) {
sb.append(current.data);
current = current.next;
}
String str = sb.toString();
int x = Integer.parseInt(str);
return x; // string converted to int
}
- 6. Наконец, основной метод:
public static void main(String[] args) {
// creating two demo lists
AddTwoNumbers list1 = new AddTwoNumbers();
list1.addNode(1);
list1.addNode(1);
list1.addNode(6);
AddTwoNumbers list2 = new AddTwoNumbers();
list2.addNode(1);
list2.addNode(9);
list2.addNode(2);
// reversing the lists
Node x1 = list1.reverse(list1.head);
Node x2 = list2.reverse(list2.head);
// getting the returned integer representation of the lists
int y1 = arr(x1);
int y2 = arr(x2);
// adding both the values that's why we did the 5th step to simplify this summing process
int sum = y1 + y2;
// convert again to string builder so that we can reverse it easily
StringBuilder str = new StringBuilder();
StringBuilder output = str.append(sum).reverse();
// create a new list that will be returned
AddTwoNumbers finalList = new AddTwoNumbers();
// pass the values to the list
for (int i = 0; i < output.length(); i++) {
int x =Integer.parseInt(String.valueOf(output.charAt(i)));
finalList.addNode(x);
}
// and, finally display it
finalList.display();
}
Я знаю, что это решение затянулось слишком надолго но это хороший способ легко решить эту проблему.
Оригинал: “https://dev.to/rajesh6161/reverse-lists-add-them-reverse-the-sum-and-return-the-sum-as-a-list-4f2o”