[数据结构与算法]【数据结构】数据结构常见链表面试题剖析（上）

反转链表

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
来自：https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/

迭代法

从头到尾让当前节点指向当前节点的前一个节点，使用next指针标记当前节点本来的下一个节点。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head==NULL){
            return NULL;
        }
        ListNode *pre=NULL;
        ListNode *cur=head;
        ListNode *next=cur->next;
        while(cur!=NULL){
            next=cur->next;
            cur->next=pre;
            pre=cur;
            cur=next;
        }
        return pre;
    }
};

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
	if head == nil {
		return nil
	}
	var pre *ListNode
	cur, next := head, head.Next
	for cur != nil {
		next = cur.Next
		cur.Next = pre
		pre = cur
		cur = next
	}
	return pre
}

头插法

新定义一个指针作为返回结果的新链表的头结点，从头到尾遍历原链表的节点，一个一个头插如新链表，实现逆序。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head==NULL){
            return NULL;
        }
        ListNode* ret=NULL;
        ListNode* cur=head;
        ListNode* next=cur->next;
        while(cur!=NULL){
            next=cur->next;
            cur->next=ret;
            ret=cur;
            cur=next;
        }
         return ret;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
func reverseList(head *ListNode) *ListNode {
	if head == nil {
		return nil
	}
	var ret *ListNode
	cur, next := head, head.Next
	for cur != nil {
		next = cur.Next
		cur.Next = ret
		ret = cur
		cur = next
	}
	return ret
}