Insert node at the end of linked list
There is a simple iterative solution for these kind of problems.
Node Insert(Node head,int data) {
Node newNode = new Node();
newNode.data = data;
if (head == null) {
return newNode;
}
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
return head;
}
It works perfectly fine. But I want to learn recursion and see the things with that perspective. Hence I came up with the below solution, it seems elegant but I have to admit that it was just intuition and the given code worked. I want to develop a mental model for working with recursion or at least some way to verify that my code will work fine. How to verify theoretically that the below solution should work.
Recursive version
Node Insert(Node head,int data) {
// Base case.
if (head == null) {
Node newNode = new Node();
newNode.data = data;
return newNode;
}
// Smaller problem instance.
head.next = Insert(head.next, data);
return head;
}
A recursive solution generally must obey these rules:
if ) to two blocks of code: the base block and the general block. Of corse, this is a simple recursion model, which in practice could be more complex (more than one base case, recursion between two functions, etc).
If we analyze theoretically your proposal according to these rules, we can see it meets all of them.
I would take the code just a little further and remove the multiple exit points. This allows you to reason about both the effect on the list and which node mut be returned.
Node appendRecursive(Node head, int data) {
// By default return the same list we were given.
Node list = head;
if (list == null) {
// At end of list or list is empty.
list = new Node();
list.data = data;
} else {
// Recurse.
head.next = appendRecursive(head.next, data);
}
return list;
}
As far as reasoning goes you generally need to use induction.
list == null ) then create a new node and that becomes your list. Given the above it is possible to reason that in all cases this will function correctly because either the list is empty or it is not.
Using recursion on lists is generally considered inefficient and clunky because iterative algorithms fit better with linear structures. A better exercise would be to write your own Tree structure because trees lend themselves very well to recursive algorithms. You will discover that it is often much easier and more elegant to perform the required function recursively on a tree.
static class Tree {
Node head = null;
class Node {
Node left;
Node right;
int data;
private Node(int data) {
this.data = data;
}
}
void insert(int data) {
head = insert(head, data);
}
private Node insert(Node node, int data) {
if (node == null) {
// Empty tree becomes just the node.
return new Node(data);
} else {
// Pick the correct branch to add this data to.
if (data < node.data) {
node.left = insert(node.left, data);
} else {
node.right = insert(node.right, data);
}
}
return node;
}
private CharSequence toString(Node n) {
StringBuilder s = new StringBuilder();
if (n != null) {
// First print the tree on the left.
if (n.left != null) {
s.append(toString(n.left)).append(",");
}
// Then the data in this node.
s.append(n.data);
// Then the tree on the right.
if (n.right != null) {
s.append(",").append(toString(n.right));
}
}
return s;
}
@Override
public String toString() {
// Even toString is recursive.
StringBuilder s = new StringBuilder("{");
s.append(toString(head));
return s.append("}").toString();
}
}
public void test() {
Tree tree = new Tree();
for (int i : new int[]{6, 5, 4, 3, 2, 1}) {
tree.insert(i);
}
System.out.println(tree);
}
Notice how simple it is to judge where to add "," in the toString method - a notoriously clunky issue when printing lists.
Node Insert(Node head,int data) {
if (head == null) {
head = new Node();
head.data = data;
}
else{
head.next = Insert(head.next, data);
}
return head;
}
Assume you have 5,3,2,1 and you want to add 4 then :- insert(node(5),int 4)
if( node(5) == null ) no then head.next = node(5).next which is node(3) and call Insert(node(3),4)
if( node(3) == null ) no then head.next = node(3).next which is node(2) and call Insert(node(2),4)
if( node(2) == null ) no then head.next = node(2).next which is node(1) and call Insert(node(1),4)
if( node(1) == null ) no then head.next = node(1).next which is null " because there are no elements after node(1) " and call Insert(node(1).next,4)
(node(1).next) == null yes then set head = new node (); and set the data head = new node (); at the end return head
上一篇: Python ElementTree：ElementTree vs根元素
下一篇: 将节点插入链表的末尾