【Java笔试题】关于ListNode的操作及测试用例的编写,以反转链表操作为例

笔试题经常会见到关于链表的操作,题目会给出ListNode类的描述如下:

public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}

这种题我一开始不知道怎么测试,不知道怎么输入一个链表,后来突然明白了,就是从一个头节点head开始,把每一个节点的next域定义一下就行了,这样就成了一个链表啦。

比如反转链表方法:

    public ListNode ReverseList(ListNode head) {
        ListNode newHead = head;
        Stack<ListNode> s = new Stack<ListNode>();
        while(head!=null){
            s.push(head);
            head = head.next;
        }
        if(!s.isEmpty()){
            newHead = s.pop();
        }
        
        ListNode t=newHead;
        while(!s.isEmpty()){
        	newHead.next = s.pop();
        	newHead = newHead.next;
        }
        newHead.next = null;//注意!一定要把最后一个节点的next置为null
        return t;
    }

这是我按照我的很朴素的想法写的,不是最优的算法。我的思路是:先把输入的链表从头开始依次放入栈中;放完之后,栈顶那个节点就是新的(链表反转之后的)头节点;然后再依次弹出栈中的节点作为头节点的next的next的next........直到栈空。注意!一定要把最后一个节点的next置为null!!!否则会陷入无限循环,因为此时最后一个节点newLastNode是旧链表的第一个节点oldFirstNode,oldFirstNode的next是指向旧链表第二个节点old2ndNode,然而old2ndNode的next现在指向的是newLastNode。

那么怎么测试这个方法呢?

在JUnit测试类中编写测试用例如下:

    @Test
    void testReverseList() {
		System.out.println("testReverseList");
		ListNode head = new ListNode(1);//创建头节点
		head.next = new ListNode(2);//再定义头节点的next域
		ListNode t = head.next;
		for(int i=3;i<10;i++) {//创建一个简单的链表{1,2,3,4,5,...,9}
			t.next = new ListNode(i);
			t = t.next;
		}
		ListNode newHead = ReverseList(head);//调用反转链表方法
		System.out.println(newHead.val);//检查新的头节点的值
		printListNode(newHead);//打印新链表的全部节点
	}
    //为了便于查看结果,写的打印链表的方法
	public void printListNode(ListNode head) {
		while(head!=null) {
			System.out.print(head.val+" ");
			head = head.next;
		}
	}	

 


版权声明:本文为zsh_edison原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接和本声明。