单链表的反转问题

单链表的反转问题

单链表反转问题经常会遇到。在此记录一下，以便查阅方便。

如果反转一个有头结点的使用下面的方法比较合适。

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

<code>//反转单链表，此单链表带有头节点。</code>

<code>//思想：使用tmp临时指针保存头结点与链表的关系</code>

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

<code>{</code>

<code>    </code><code>int</code> <code>data;</code>

<code>    </code><code>struct</code> <code>ListNode * next;</code>

<code>}ListNode,*LinkList;</code>

<code>void</code> <code>ReverseList(ListNode* Head)</code>

<code>    </code><code>ListNode *current,*tmp;</code>

<code>    </code><code>current = Head-&gt;next;</code>

<code>    </code><code>if</code><code>(current != NULL)</code><code>//反转后第一个节点的后继要为NULL</code>

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

<code>        </code><code>tmp = current;</code>

<code>        </code><code>current = current-&gt;next;</code>

<code>        </code><code>tmp-&gt;next = NULL;</code>

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

<code>    </code> 

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

<code>        </code><code>tmp-&gt;next = Head-&gt;next;</code>

<code>        </code><code>Head-&gt;next = tmp;</code>

<code>}</code>

如果没有头结点，下面的反转比较合适

<code>//如果没有头节点，下面的函数比较适合</code>

<code>//思想：使用pre和next两个指针来记录当前处理的节点的前一个节点和后一个节点的信息</code>

<code>ListNode * ReverseLinkList(ListNode * head)</code>

<code>    </code><code>ListNode * pre,*next;</code>

<code>    </code><code>pre = NULL;</code>

<code>    </code><code>next = NULL;</code>

<code>    </code><code>while</code><code>(head)</code>

<code>        </code><code>next = head-&gt;next;</code>

<code>        </code><code>head-&gt;next = pre;</code>

<code>        </code><code>pre = head;</code>

<code>        </code><code>head = next;</code>

<code>    </code><code>return</code> <code>pre;</code>

<code></code>

本文转自313119992 51CTO博客，原文链接:http://blog.51cto.com/qiaopeng688/1837429