【劍指offer】面試題24：反轉連結清單

完整代碼位址

完整代碼位址

題目

定義一個函數，輸入一個連結清單的頭結點，反轉該連結清單并輸出反轉後連結清單的頭結點

思路

很簡單，單純考察代碼的魯棒性

要針對區分成以下三種情況處理：

1.輸入的連結清單頭指針為null

2.輸入的連結清單隻有一個節點

3.輸入的連結清單有多個節點（正常情況）

代碼

public static class ListNode {
    public int val;
    public ListNode next = null;
    public ListNode(int val) {
        this.val = val;
    }
}

public static ListNode ReverseList(ListNode head) {
    // 長度為0或1
    if(head == null || head.next == null)
        return head;

    ListNode first = head;
    ListNode second = head.next;
    head.next = null;
    ListNode third;
    while(second != null) {
        third = second.next;
        second.next = first;
        first = second;
        second = third;
    }
    return first;
}
           

測試

public static void main(String[] args) {
    test1();
    test2();
    test3();
}

/**
 * 功能測試
 */
private static void test1() {
    ListNode node1 = new ListNode();
    ListNode node2 = new ListNode();
    ListNode node3 = new ListNode();
    ListNode node4 = new ListNode();
    node1.next = node2;
    node2.next = node3;
    node3.next = node4;

    // 4-3-2-1
    node1 = _24_ReverseList.ReverseList(node1);
    printList(node1);
}

/**
 * 邊界測試
 * 長度為1
 */
private static void test2() {
    ListNode node1 = new ListNode();
    node1 = _24_ReverseList.ReverseList(node1);
    printList(node1);
}

/**
 * 極端測試 
 */
private static void test3() {
    ListNode node1 = _24_ReverseList.ReverseList(null);
    printList(node1);
}

private static void printList(ListNode head) {
    ListNode cur = head;
    while(cur != null) {
        System.out.print(cur.val + " ");
        cur = cur.next;
    }
    System.out.println();
}