如何實現翻轉鏈表

這篇文章為大家分享實現翻轉鏈表的一道算法題。文章這道題使用了遞歸和棧等方法實現翻轉鏈表，希望大家通過這篇文章能有所收獲。

1 題目

每K個節點一組進行翻轉,剩下不足K個的保留原狀.

2 直接翻轉

將鏈表分成三部分，已翻轉，待翻轉，未翻轉三部分：

首先，用一個指針t表示要插入的位置的前驅，一邊把head移動k遍，一邊插入在t后面（下圖假設k=3）：

int i=0;
for(;i<k && head != null;++i)
{
    temp = head.next;
    head.next = t.next;
    t.next = head;
    head = temp;
}

直接插在t的后面，一輪循環之后，移動t與head.

t的新位置為未插入head之前的head的位置，因此在插入之前把head的位置保存下來，直接使t移動到該位置，head的位置為自然移動到的位置，不需改變。

ListNode nextTPosition = head;
ListNode temp;
int i=0;
for(;i<k && head != null;++i)
{
    temp = head.next;
    head.next = t.next;
    t.next = head;
    head = temp;
}
if(i == k)
    t = nextTPosition;

接著再翻轉，到達7后，7不需要翻轉，因為剩下的節點數不足：

這時就需要i發揮作用了，i表示已翻轉的節點的值，因為只是一次遍歷，每遍歷k次便翻轉k次，若i小于k，由于已經翻轉了剩下的i個節點，因此需要再將這剩下的i個節點翻轉一次：

if(i == k)
    t = nextTPosition;
else
{
    for(head = t.next,t.next=null;head!=null;)
    {
        temp = head.next;
        head.next = t.next;
        t.next = head;
        head = temp;
    }
    break;
}

對剩下的i個節點再次翻轉時，不需要修改t的位置，使head指向t.next，再把t.next置為null，因為此時t為

4->7

若不把t.next置為null，在

head.next = t.next

這一步會使head.next指向錯誤的t.next，導致會在最后一個節點不斷循環。
翻轉最后的i個節點后，跳出循環，返回結果。

3 遞歸

遞歸的話思路也類似，遍歷k次，翻轉k個，若還有需要翻轉的節點，遞歸翻轉，若沒有，翻轉剩下的i個節點。

if(i == k)
    t.next = reverse(head,k);

大部分代碼與循環相同就不貼了，最大的不同是這里，這里的t為原來未遍歷前的head，因為改成遞歸后，不需要使用t作為移動的指針指示插入的位置，t.next就相當于翻轉后的最后一個節點，把遞歸的結果插入到這個節點的后面。

4 使用額外空間--棧

因為題目規定只能使用常數的額外空間，因此應該只有這兩種方法了，但是，如果允許使用額外的空間，可以使用棧優化直接翻轉的算法。

因為出棧的次序正是翻轉的順序，每遍歷k個節點就壓棧k個節點，若剩余不足k個節點，把head連上dummy，若還有多余的節點或者剛好遍歷完，把出棧的節點依次連上主鏈。

while(true)
{
    Stack<ListNode> s = new Stack<>();
    ListNode temp = head;
    int i=0;
    for(;i<k && head != null;++i)
    {
        s.add(new ListNode(head.val));
        head = head.next;
    }
    if(i == k)
    {
        for(i=0;i<k;++i)
        {
            t.next = s.pop();
            t = t.next;
        }
    }
    else if(head == null)
    {
        t.next = temp;
        break;
    }
}

其中for循環為遍歷壓棧，i==k判斷是否翻轉鏈表。

關于實現翻轉鏈表就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果喜歡這篇文章，不如把它分享出去讓更多的人看到。