反轉連結清單的幾種模式

​連結清單作為一種常用的資料結構，面試當然也是家常便飯。此處就來談談關于連結清單面試中的的幾種常見反轉。

1.逆序所有節點

輸入：list = 1->2->3->4->5->null

輸出：list = 5->4->3->2->1->null

思路：定義previous、current、next（即前驅、目前、後繼）指針。從頭結點開始往後一個個逆序，即不斷讓current.next = previous即可。

JAVA參考代碼

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

public ListNode reverse(ListNode current) {
    ListNode previous = null; //前驅結點
    while (current != null) {
        //next記錄下一個節點，current是目前節點
        ListNode next = current.next;
        current.next = previous;
        previous = current;
        current = next;
    }
    return previous;
}

           

2.逆序第m到n個節點(1 ≤ m ≤ n ≤ size)

輸入: list = 1->2->3->4->5->6->null, m = 2 and n = 5,

輸出: list = 1->5->4->3->2->6->null

思路：找出原連結清單中第m到n個元素，進行逆序後。再接回原來的連結清單中。

• a.找出原連結清單中m的前一個結點mPrevNode；
• b.取出原連結清單第m到n個元素，進行逆序；
• c.記錄原連結清單中n的下一個結點nNextNode；
• d.原連結清單結點mPrevNode指向逆序後的頭結點；
• e.逆序後的尾結點指向原連結清單結點nNextNode。

JAVA參考代碼

public ListNode reverse4Range(ListNode head, int m, int n) {
    if (m >= n || head == null) {
        return head;
    }

    ListNode newList = new ListNode(0);
    newList.next = head;
    head = newList;

    for (int i = 1; i < m; i++) {
        if (head == null) {
            return null;
        }
        head = head.next;
    }

    ListNode mPreNode = head;
    ListNode mNode = head.next;
    ListNode nNode = mNode, nNextNode = mNode.next;
    for (int i = m; i < n; i++) {
        if (nNextNode == null) {
            return null;
        }
        ListNode temp = nNextNode.next;
        nNextNode.next = nNode;
        nNode = nNextNode;
        nNextNode = temp;
    }
    mNode.next = nNextNode;
    mPreNode.next = nNode;

    return newList.next;
}
           

3.按K個值分組逆序

即從頭結點開始每k個逆序，若小于k個則不做處理。

輸入：list = 1->2->3->4->5->null, k=3

輸出：list = 3->2->1->4->5->null

思路：順序按k個一組執行逆序

• a.記錄前一個k組逆序的尾結點 prevTail；
• b.記錄下一組的頭結點 nextGroupHead；
• c.找到k個結點則進行該組逆序， 若不足k個則直接指向後結點；
• d.前一個尾結點 prevTail 指向逆序後的頭結點 reverseHead。

JAVA參考代碼

public ListNode reverse4KGroup(ListNode head, int k) {
    ListNode newList = new ListNode(0);
    ListNode prevTail = newList;
    ListNode nextGroupHead = head;
    while (head != null) {
        for (int i = 0; i < k-1 && head != null; i++) {
            head = head.next;
        }

        if (head != null) {
            ListNode nextHead = head.next;
            head.next = null;
            ListNode reverseHead = reverse(nextGroupHead); // 題1中的reverse()
            prevTail.next = reverseHead;
            prevTail = nextGroupHead;
            nextGroupHead = nextHead;
            head = nextGroupHead;
        } else {
            prevTail.next = nextGroupHead;
        }
    }
    return newList.next;
}

public ListNode reverse(ListNode current) {
    ListNode previous = null; //前驅結點
    while (current != null) {
        //next記錄下一個節點，current是目前節點
        ListNode next = current.next;
        current.next = previous;
        previous = current;
        current = next;
    }
    return previous;
}
           

更多文章歡迎掃碼關注公衆号 [JAVA覓音閣] 檢視