链表问题全解(补充待续)

删除倒数第Nth节点

Specification

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：

给定的 n 保证是有效的。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

Implementation(#1)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(head==NULL || n < 1)return NULL;
        ListNode *current = head;
        while(current!= NULL)
        {
            n--;
            current = current->next;
        }
        if(n == 0)
        {
            ListNode *tmp = head;
            head = head->next;
            delete tmp;
        }
        else if (n<0)
        {
            ListNode* cur = head;
            while(++n != 0)
            {
                cur = cur->next;
            }
            ListNode* deleteNode = cur->next;
            cur->next = deleteNode->next;
            delete deleteNode;
        }
        return head;
    }
};

Implementation (#2)

为了方便，我们假设**n**是有效的

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        
        if(head == NULL || n < 1) return head;
        ListNode* fakeHead = new ListNode(0);
        fakeHead->next = head;
        ListNode* Right = fakeHead;
        for(int i=0;i<n+1;i++)
        {
            Right = Right->next;

        }
        ListNode* Left = fakeHead;
        while(Right!=NULL)
        {
            Left=Left->next;
            Right=Right->next;
        }
        
        ListNode* tmp = Left->next;
        Left->next = tmp->next;
        delete tmp;
        return fakeHead->next;
    }

};

翻转单项链表

Requirement

如果链表长度为N，那么时间复杂度要求为O(N)。额外的空间复杂度为O(1)。

Implementation (#1)

/**
 * 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 head;
        ListNode* NewHead = NULL;
        ListNode* next    = NULL;
        ListNode* current = head;
        while(current != NULL)
        {
            next          = current->next;
            current->next = NewHead;
            NewHead       = current;
            current       = next;
        }
          //返回新的头节点
          return NewHead;
        
    }
};

反转双向链表

Requirement

The same

Implementation

class Node
{
	public:
  		int val;
  		Node *next;
  		Node* pre;
  		Node(int data):val(data){}
};
Node* reverseList(Node* head)
{
  Node* NewHead = null;
  Node* next = null;
 	Node* current = head;
  while(current != null)
  {
    //保存当前的下一个节点
    next = current->next;
    //当前节点的下一个此时应该指向已完成反转的部分的头一个也就是新的头结点
    current->next = NewHead;
    current->pre  = next;
    //新的头节点只想新添加的节点
    NewHead = current;
    //更新当前需要处理的节点
    current = next;
  }
  //返回新的头节点
  return NewHead;
}

反转部分单项链表

Requirement

给定一个单项链表的头节点head；以及两个Integer： from & to，在单向链表上把第from个节点到第to个节点这一部分反转。

时间复杂度为O(N)

解题思路

个人还是更加喜欢LeetCode里Crunch的解法，思路非常清晰。同时，运用一个虚拟的头结点（即 dummy Head）是我比较喜欢的的一种做法，因为这样可以规避掉头结点可能被替换的问题，函数最后只需要返回dummy head->next 即可。首先获得第一个开始变换的节点的前一个节点，然后，痛过从第M个节点一直到第N个节点的循环替换。

Implementation

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if(head==NULL) return NULL;
        ListNode* cur = head;
        int len=0;
        while(cur!=NULL)
        {
            cur = cur->next;
            len++;
        }
        //m 和 n 的合法性检查
        if(m < 0 || n >len || m>n)
        {
            return head;
        }
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* pre = dummyHead;
        for(int i = 0;i<m-1; i++)
        {
            pre = pre->next;
        }
        ListNode* current = pre->next;
        for(int i = m; i<n;i++)
        {
            ListNode* tmp = current->next;
            current->next = tmp->next;
            tmp->next = pre->next;
            pre->next = tmp;
        }
        return dummyHead->next;
    }
};

合并两个有序链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-two-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

这道题用递归的思路去做还是比较好理解的，当然在空间复杂度就没办法很好的解决。

首先考虑的时base case的问题 也就是便捷问题，如果有空的list， 就直接返回NULL即可。

然后我们根据ascending order的要求比较两边当前节点的数值大小，去较小值，然后递归决定下一添加到结果里的值。

Implementation

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1 == NULL) return l2;
        if(l2 == NULL) return l1;
        
        if(l1->val < l2->val)
        {
            l1->next = mergeTwoLists(l1->next,l2);
            return l1;
        }
        else
        {
            l2->next = mergeTwoLists(l1,l2->next);
            return l2;
        }
        
    }
};