單向鏈結串列的反轉

如果鏈結串列如下:

number	1	2	3	4	5	6	7	8	9
name	Peter1	Peter2	Peter3	Peter4	Peter5	Peter6	Peter7	Peter8	Peter9
next (指標)	指向2號節點	指向3號節點	指向4號節點	指向5號節點	指向6號節點	指向7號節點	指向8號節點	指向9號節點	NULL

改成這樣:

number	1	2	3	4	5	6	7	8	9
name	Peter1	Peter2	Peter3	Peter4	Peter5	Peter6	Peter7	Peter8	Peter9
next (指標)	NULL	指向1號節點	指向2號節點	指向3號節點	指向4號節點	指向5號節點	指向6號節點	指向7號節點	指向8號節點

做一個反轉,應該如何做??

我們先使用1,2,3號節點的位置,把1號節點的next設為Null.

再把2號的next指向1號節點,

接著使用2,3,4號節點.

再把3號的next指向2號節點,

接著使用3,4,5號節點.

再把4號的next指向3號節點,

接著使用4,5,6號節點.

...........................

接著使用7,8,9號節點.

將8號節點的next指向7號節點,

發現9號節點next是NULL,跳出迴圈.

把9號節點的next指向8號,接著把head(頭指標)指向9號節點,大公告成.

每一次迴圈次需要使用3個節點,把第2個節點的next指向第1個節點,

下一次的第一個節點是這一次的第二個節點,

下一次的第二個節點是這一次的第三個節點.

下一次的第三個節點是這一次的第三個節點的next.

struct node{
    int data;
    struct node *link;
};
void reverse()
{
    struct node *p = first,
                *q = NULL,
                *r;
    while (p != NULL)
    {
        r = q;
        q = p;
        p = p->link;
        q->link = r;
    }
    q = first;
}

參考自

http://home.educities.edu.tw/peterhuang1/DataStruct/DataLinkReturn.htm