LeetCode——链表

内容概览

   包含8道链表常考题目，如下：

206 反转链表（easy）

   题目描述： 反转一个单链表。
   示例：

输入：1->2->3->4->5->NULL
输出：5->4->3->2->1->NULL

   思路： 依次遍历链表节点，每遍历一个节点即逆置一个节点。

题解：

class Solution {
public:
	ListNode* reverseListNode ( ListNode* head ) {
		ListNode* new_head = NULL;
		while ( head ) {
			ListNode* next = head -> next;   // 备份 head->next
			head -> next = new_head;          // 更新 head->next
			new_head = head;                    // 移动 new_head
			head = next; 					// 遍历链表
		}
		return new_head;				//返回新链表的头节点
}

---

91 反转链表||（medium）

   题目描述： 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
   说明： 1 ≤ m ≤ n ≤ 链表长度。
   示例：

输入：1->2->3->4->5->NULL, m = 2, n = 4
输出：1->4->3->2->5->NULL

   思路： 依次遍历链表节点，每遍历一个节点即逆置一个节点。

题解：

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        int change_len = n - m + 1;
        ListNode* pre_head = NULL;
        ListNode* result = head;
        while(head && --m){
            pre_head = head;
            head = head -> next;
        }
        ListNode* modify_list_tail = head;
        ListNode* new_head = NULL;
        while(head && change_len){
            ListNode* next = head -> next;
            head -> next = new_head;
            new_head = head;
            head = next;
            change_len--;
        }
        modify_list_tail -> next = head;
        if(pre_head){
            pre_head -> next = new_head;
        }
        else{
           result = new_head;
        }
        return result;
    }
}