高效代码之反转单链表

高效代码之反转单链表

单链表的反转是经常用到的

那么单链表的高效转换就很重要了。这里记录一下。方便用时查阅。

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