高效代碼之反轉單連結清單

高效代碼之反轉單連結清單

單連結清單的反轉是經常用到的

那麼單連結清單的高效轉換就很重要了。這裡記錄一下。友善用時查閱。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

<code>struct</code> <code>ListNode</code>

<code>{</code>

<code>    </code><code>int</code> <code>m_nValue;</code>

<code>    </code><code>ListNode * m_pNext;</code>

<code>};</code>

<code>//實作如下：</code>

<code>//反轉連結清單需要3個指針</code>

<code>//1.指向目前元素pNode</code>

<code>//2.指向目前元素的前一個元素pPrev</code>

<code>//3.指向目前元素的後一個元素pNext</code>

<code>ListNode* ReverseList(ListNode* pHead)</code>

<code>    </code><code>ListNode* pReverseHead = NULL;</code>

<code>    </code><code>ListNode* pNode = pHead;</code>

<code>    </code><code>ListNode* pPrev = NULL;</code>

<code>    </code><code>while</code><code>(pNode != NULL)</code>

<code>    </code><code>{</code>

<code>        </code><code>ListNode* pNext = pNode-&gt;m_pNext;</code>

<code>        </code><code>if</code><code>(pNext == NULL)</code>

<code>        </code><code>{</code>

<code>            </code><code>pReverseHead = pNode;</code>

<code>        </code><code>}</code>

<code>        </code><code>pNode-&gt;m_pNext = pPrev;</code>

<code>        </code><code>pPrev = pNode;</code>

<code>        </code><code>pNode = pNext;</code>

<code>    </code><code>}</code>

<code>    </code><code>return</code> <code>pReverseHead;</code>

<code>}</code>

參考自：劍指offer

本文轉自313119992 51CTO部落格，原文連結:http://blog.51cto.com/qiaopeng688/1845340