java链表递归的另一种实现方法

这是一个linked list， 其中的一个method是给每个值+上一个x， 我理解递归思路，但是我想知道不用递归，iterative 的方式如何写。

public class IntList {
public int first;
public IntList rest;

public IntList(int f, IntList r) {
first = f;
rest = r;
}

/** Return the size of the list using... recursion! */
public int size() {
if (rest == null) {
return 1;
}
return 1 + this.rest.size();
}

/** Return the size of the list using no recursion! */
public int iterativeSize() {
IntList p = this;
int totalSize = 0;
while (p != null) {
totalSize += 1;
p = p.rest;
}
return totalSize;
}

/** Returns the ith value in this list.*/
public int get(int i) {

}

/** Returns an IntList identical to L, but with
* each element incremented by x. L is not allowed
* to change. */
/**我想知道这个incrList method不用递归，如何用iterative 的方式写出来 */
public static IntList incrList(IntList L, int x) {
if (L == null) {
return L;
}
IntList incr = new IntList(L.first + x, incrList(L.rest, x));
return incr; 
}

public static void main(String[] args) {
IntList L = new IntList(15, null);
L = new IntList(10, L);
L = new IntList(5, L);

System.out.println(L.iterativeSize());
}
} 

public class IntList {
    public int first;
    public IntList rest;

    public IntList(int f, IntList r) {
        first = f;
        rest = r;
    }

    /**
     * Return the size of the list using... recursion!
     */
    public int size() {
        if (rest == null) {
            return 1;
        }
        return 1 + this.rest.size();
    }

    /**
     * Return the size of the list using no recursion!
     */
    public int iterativeSize() {
        IntList p = this;
        int totalSize = 0;
        while (p != null) {
            totalSize += 1;
            p = p.rest;
        }
        return totalSize;
    }


/**
 * Returns an IntList identical to L, but with
 * each element incremented by x. L is not allowed
 * to change.
 *
 */
    /**
     * 我想知道这个incrList method不用递归，如何用iterative 的方式写出来
     */
    public static IntList incrList(IntList L, int x) {
        if (L == null) {
            return L;
        }
        IntList incr = new IntList(L.first + x, incrList(L.rest, x));
        return incr;
    }

    public static IntList incrList2(IntList L, int x) {
        if (L == null) {
            return L;
        }
        IntList temp = L;
        IntList incr = new IntList(temp.first + x, null);
        IntList temp2 = incr;
        while (temp.rest != null) {
            temp = temp.rest;
            temp2.rest = new IntList(temp.first + x, null);
            temp2 = temp2.rest;
        }
        return incr;
    }

    @Override
    public String toString() {
        return "IntList{" +
                "first=" + first +
                ", rest=" + rest +
                '}';
    }

    public static void main(String[] args) {
        IntList L = new IntList(15, null);
        L = new IntList(10, L);
        L = new IntList(5, L);
        System.out.println(L);
        System.out.println(IntList.incrList2(L, 1));
    }
}

代码修改如下:

public class IntList {
    public int first;
    public IntList rest;

    public IntList(int f, IntList r) {
        first = f;
        rest = r;
    }

    /**
     * Return the size of the list using... recursion!
     */
    public int size() {
        if (rest == null) {
            return 1;
        }
        return 1 + this.rest.size();
    }

    /**
     * Return the size of the list using no recursion!
     */
    public int iterativeSize() {
        IntList p = this;
        int totalSize = 0;
        while (p != null) {
            totalSize += 1;
            p = p.rest;
        }
        return totalSize;
    }


    /** Returns the ith value in this list.*/
//    public int get(int i) {
//
//    }

/** Returns an IntList identical to L, but with
 * each element incremented by x. L is not allowed
 * to change. */
    /**
     * 我想知道这个incrList method不用递归，如何用iterative 的方式写出来
     */
    public static IntList incrList(IntList L, int x) {
//        if (L == null) {
//            return L;
//        }
//        IntList incr = new IntList(L.first + x, incrList(L.rest, x));
//        return incr;
        IntList reverseL = null;
        while (L != null) {
            reverseL = new IntList(L.first, reverseL);
            L = L.rest;
        }
        IntList incr = null;
        while (reverseL != null) {
            incr = new IntList(reverseL.first + x, incr);
            reverseL = reverseL.rest;
        }
        return incr;
    }

    public static void main(String[] args) {
        IntList L = new IntList(15, null);
        L = new IntList(10, L);
        L = new IntList(5, L);
//        System.out.println(L.iterativeSize());

        L = incrList(L, 1);


        while (L != null) {
            System.out.println(L.first);
            L = L.rest;
        }

    }
}

测试输出 (每个值+1):

6
11
16

Process finished with exit code 0

如果要使用迭代方式实现 incrList 方法，可以遍历整个链表，并在遍历过程中将每个节点的值加上给定的 x。代码如下：

```java
public static IntList incrList(IntList L, int x) {
    IntList p = L;
    while (p != null) {
        p.first += x;
        p = p.rest;
    }
    return L;
}

```
这个代码从第一个节点开始遍历整个链表，在每个节点上加上给定的x，并将指针指向下一个节点，最后返回原链表的引用。

如果我 的回答 对您有帮助，请及时采纳

递归和迭代一把情况下，都是可以相互转换的。迭代一般是三个步骤：

• 第一个：迭代遍历初始化值。
• 第二个：找出迭代公式。
• 第三个：迭代结束条件。

public static IntList incrList(IntList L, int x) {
    IntList head = L; 
    while (L != null) {
        L.first += x;
        L = L.rest;
    }
    return head;
}