Linked List Swap Nodes in Pairs Sort List Rotate List Reverse Nodes in k-Group Reverse Linked List Reverse Linked List II Reorder List Remove Nth Node From End of List Remove Linked List Elements Remove Duplicates from Sorted List Remove Duplicates from Sorted List II Partition List Palindrome Linked List Merge Two Sorted Lists Merge k Sorted Lists Linked List Cycle Linked List Cycle II Intersection of Two Linked Lists Insertion Sort List Delete Node in a Linked List Copy List with Random Pointer Convert Sorted List to Binary Search Tree Add Two Numbers 所有代碼下載LeetCode-Linked List
Given a linked list, swap every two adjacent nodes and return its head.
For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.
Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.
參考：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* swapPairs(struct ListNode* head) {
//空鏈表和單一節點鏈表，不作處理
if(NULL == head || NULL == head->next) return head;
struct ListNode *p1, *p2, *pPre, *pNext;
p1 = head, p2 = head->next;
//第一對節點，做特殊處理
pNext = p2->next;
p2->next = p1;
p1->next = pNext;
pPre = p1;
head = p2; //這一句是特殊處理的理由
while(pNext)
{
p1 = pNext;
p2 = p1->next;
if(NULL == p2) break;
pNext = p2->next;
//以下兩句代碼：逆置相鄰節點
p2->next = p1;
p1->next = pNext;
pPre->next = p2;
pPre = p1;
}
return head;
}
Sort a linked list in O(n log n) time using constant space complexity.
參考1：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
#include
class Solution {
public:
ListNode* sortList(ListNode* head) {
if(NULL == head || NULL == head->next){
return head;
}
vector vec;
ListNode *p = head;
while(p){
vec.push_back(p->val);
p = p->next;
}
sort(vec.begin(), vec.end()); //n*logn
p = head;
int i = 0;
while(p){
p->val = vec[i];
i++;
p = p->next;
}
return head;
}
};
參考2：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* merge(struct ListNode *head1, struct ListNode *head2)
{
if(NULL == head1) return head2;
if(NULL == head2) return head1;
struct ListNode *head = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode *p = head;
p->next = NULL;
while(head1 && head2)
{
if(head1->val < head2->val)
{
p->next = head1;
head1 = head1->next;
}
else
{
p->next = head2;
head2 = head2->next;
}
p = p->next;
}
if(head1)
{
p->next = head1;
}
if(head2)
{
p->next = head2;
}
struct ListNode *temp = head;
head = head->next;
free(temp); //釋放頭節點
return head;
}
struct ListNode* mergeSort(struct ListNode *head)
{
if(NULL == head || NULL == head->next) return head;
//使用快慢指針，尋找中間節點，從而鏈表一分為二
struct ListNode *slow, *fast, *p;
slow = fast = head;
while(fast)
{
fast = fast->next;
if(fast)
{
fast = fast->next;
if(NULL == fast) break;
}
else break;
slow = slow->next;
}
//此時slow即是中間節點
p = slow->next;
slow->next = NULL;
struct ListNode *pLeft = mergeSort(head);
struct ListNode *pRight = mergeSort(p);
return merge(pLeft, pRight);
}
struct ListNode* sortList(struct ListNode* head) {
if(NULL == head || NULL == head->next) return head;
return mergeSort(head);
}
Given a list, rotate the list to the right by k places, where k is non-negative.
For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.
參考：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* rotateRight(struct ListNode* head, int k) {
if(NULL == head || NULL == head->next || 0 == k) return head;
struct ListNode *p, *pEnd;
p = pEnd = head;
int n = 1;
while(pEnd->next)
{
pEnd = pEnd->next;
n++;
}
k %= n; //規范k值
k = n - k;
k--;
while(k)
{
p = p->next;
k--;
}
pEnd->next = head;
head = p->next;
p->next = NULL;
return head;
}
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
You may not alter the values in the nodes, only nodes itself may be changed.
Only constant memory is allowed.
For example,
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5
參考：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseKGroup(struct ListNode* head, int k) {
if(NULL == head || NULL == head->next || k < 2) return head;
int i, n;
n = 0;
struct ListNode *p = head;
while(p){
n++;
p = p->next;
}
struct ListNode *pPre, *pCur, *pNext;
struct ListNode *pStart, *pEnd;
pStart = head;
if(n >= k){
pPre = pStart, pCur = pStart->next;
i = 1;
while(i < k){
pNext = pCur->next;
pCur->next = pPre;
pPre = pCur;
pCur = pNext;
i++;
}
pEnd = pStart;
pEnd->next = pCur;
head = pPre;
n -= k;
}
while(n >= k){
pStart = pCur;
pPre = pStart, pCur = pStart->next;
i = 1;
while(i < k){
pNext = pCur->next;
pCur->next = pPre;
pPre = pCur;
pCur = pNext;
i++;
}
pEnd->next = pPre;
pStart->next = pCur;
pEnd = pStart;
n -= k;
}
return head;
}
Reverse a singly linked list.
參考1：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head) {
if (NULL == head || NULL == head->next) return head;
struct ListNode *pPre, *pCur, *pNext;
pPre = head, pCur = head->next;
while (pCur)
{
pNext = pCur->next;
if (pPre == head) pPre->next = NULL;
pCur->next = pPre;
pPre = pCur;
pCur = pNext;
}
head = pPre;
return head;
}
參考2：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *reverseList(struct ListNode *head)
{
if (NULL == head || NULL == head->next) return head;
struct ListNode *pPre, *pCur, *pNext;
pPre = head, pCur = head->next;
while (pCur)
{
pNext = pCur->next;
pCur->next = pPre;
pPre = pCur;
pCur = pNext;
}
head->next = NULL;
head = pPre;
return head;
}
Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,
return 1->4->3->2->5->NULL.
參考：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseBetween(struct ListNode* head, int m, int n) {
if(NULL == head || NULL == head->next || m <= 0 || m >= n){
return head;
}
int len = 0;
struct ListNode *p = head;
while(p){
len++;
p = p->next;
}
if(n > len){
return head;
}
struct ListNode *pPre, *pStart, *pCur, *pNext;
int i = 1;
pPre = NULL, pStart = head;
while(i < m){
i++;
pPre = pStart;
pStart = pStart->next;
}
p = pStart;
pCur = p->next;
while(i < n){
pNext = pCur->next;
pCur->next = p;
p = pCur;
pCur = pNext;
i++;
}
if(NULL == pPre){
head = p;
}
else{
pPre->next = p;
}
pStart->next = pCur;
return head;
}
Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
You must do this in-place without altering the nodes' values.
For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.
參考：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
void reorderList(struct ListNode* head) {
//空鏈表、單個節點或雙節點都不用處理
if (NULL == head || NULL == head->next || NULL == head->next->next) return;
//尋找中間節點
struct ListNode *fast, *slow;
struct ListNode *pCur, *pPre, *pNext;
struct ListNode *p1, *p2, *p;
int flag1, flag2, n;
flag1 = 2, n = 1;
fast = slow = head;
while (fast)
{
fast = fast->next;
if (fast)
{
fast = fast->next;
if (NULL == fast)
{
flag2 = 2; //偶數個節點
break;
}
}
else
{
flag2 = 1; //奇數個節點
break;
}
slow = slow->next;
n++;
}
if (slow->next->next)
{
pPre = slow->next;
pCur = pPre->next;
while (pCur)
{
pNext = pCur->next;
pCur->next = pPre; //逆置
if (pPre == slow->next) pPre->next = NULL; //置空，作為新的鏈表結尾
pPre = pCur;
pCur = pNext;
}
slow->next = pPre; //連接
}
//將前後兩部分合並
p = head, p1 = head->next, p2 = slow->next;
while (n)
{
if ((flag2 == 1 && p == slow) || (flag2 == 2 && p->next == NULL)) break;
if (flag1 == 1)
{
p->next = p1;
p = p1;
if (p1) p1 = p1->next;
flag1 = 2;
}
else
{
p->next = p2;
p = p2;
if (p2) p2 = p2->next;
flag1 = 1;
}
}
p->next = NULL;
}
Given a linked list, remove the nth node from the end of list and return its head.
For example,
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:
Given n will always be valid.
Try to do this in one pass.
參考：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
if(NULL == head || n <= 0){
return head;
}
int len = 0;
ListNode *p = head;
while(p){
len++;
p = p->next;
}
if(n >= len){
n = len;
}
if(n == len){
head = head->next;
}
else{
int i = 1;
p = head;
while(i < len - n){
i++;
p = p->next;
}
p->next = p->next->next;
}
return head;
}
Remove all elements from a linked list of integers that have value val.
Example
Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6
Return: 1 --> 2 --> 3 --> 4 --> 5
參考：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* removeElements(struct ListNode* head, int val) {
ListNode *p, *q;
while(head && head->val == val){
p = head;
head = head->next;
//delete p;
}
if(NULL == head || NULL == head->next){
return head;
}
p = head;
while(p){
q = p->next;
while(q && q->val == val){
q = q->next;
}
p->next = q;
p = q;
}
return head;
}
Given a sorted linked list, delete all duplicates such that each element appear only once.
For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.
參考：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* deleteDuplicates(struct ListNode* head) {
if(NULL == head || NULL == head->next){
return head;
}
ListNode *p1, *p2;
p1 = head;
while(1){
p2 = p1->next;
while(p2 && p2->val == p1->val){
p2 = p2->next;
}
p1->next = p2;
p1 = p2;
if(p2 == NULL){
break;
}
}
return head;
}
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.
參考：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
#include
Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.
參考：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
#include
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
if(NULL == head) return head;
vector vec;
ListNode *p = head;
while(p)
{
vec.push_back(p->val);
p = p->next;
}
//先把小於x的數放進去
p = head;
for(int i = 0; i < vec.size(); i++)
{
if(vec[i] < x)
{
p->val = vec[i];
p = p->next;
}
}
//最後把不小於x的數放進去
for(int i = 0; i < vec.size(); i++)
{
if(vec[i] >= x)
{
p->val = vec[i];
p = p->next;
}
}
return head;
}
};
Given a singly linked list, determine if it is a palindrome.
Follow up:
Could you do it in O(n) time and O(1) space?
參考：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
#include
class Solution {
public:
bool isPalindrome(ListNode* head) {
if(NULL == head || NULL == head->next){
return true;
}
vector vec;
ListNode *p = head;
while(p){
vec.push_back(p->val);
p = p->next;
}
int size = vec.size();
for(int i = 0; i <= size / 2; i++){
if(vec[i] != vec[size - 1 - i]){
return false;
}
}
return true;
}
};
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
參考：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
if(NULL == l1){
return l2;
}
if(NULL == l2){
return l1;
}
struct ListNode *head, *p1, *p2, *p;
int flag = 0;
p1 = l1, p2 = l2;
if(p1->val < p2->val){
head = p1;
p1 = p1->next;
flag = 1;
}
else{
head = p2;
p2 = p2->next;
flag = 2;
}
p = head;
while(p1 && p2){
if(flag == 1){
while(p1 && (p1->val <= p2->val)){
p1 = p1->next;
p = p->next;
}
if(!p1 || !p2){
break;
}
p->next = p2;
p2 = p2->next;
p = p->next;
flag = 2;
}
else{
while(p2 && (p2->val <= p1->val)){
p2 = p2->next;
p = p->next;
}
if(!p1 || !p2){
break;
}
p->next = p1;
p1 = p1->next;
p = p->next;
flag = 1;
}
}
if(p1){
p->next = p1;
}
if(p2){
p->next = p2;
}
return head;
}
Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
參考：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
bool hasCycle(struct ListNode *head) {
if (NULL == head || NULL == head->next) {
return false;
}
struct ListNode *p1, *p2;
p1 = head, p2 = head->next;
while (true) {
if (NULL == p2) {
false;
}
if (p1 == p2) {
return true;
}
p1 = p1->next;
if (NULL == p2->next) {
return false;
}
else {
p2 = p2->next;
if (NULL == p2->next) {
return false;
}
p2 = p2->next;
}
}
}
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Note: Do not modify the linked list.
Follow up:
Can you solve it without using extra space?
參考：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
bool hasCycle(struct ListNode *head, struct ListNode **encounter)
{
if(NULL == head) return false;
struct ListNode *fast, *slow;
fast = slow = head;
while(fast)
{
fast = fast->next;
if(NULL == fast) return false;
else fast = fast->next;
slow = slow->next;
if(fast == slow)
{
*encounter = fast;
return true;
}
}
return false;
}
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode *encounter = NULL;
if(false == hasCycle(head, &encounter)) return NULL;
struct ListNode *p = head;
while(p != encounter)
{
p = p->next;
encounter = encounter->next;
}
return p;
}
Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:
A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
begin to intersect at node c1.
Notes:
If the two linked lists have no intersection at all, return null.
The linked lists must retain their original structure after the function returns.
You may assume there are no cycles anywhere in the entire linked structure.
Your code should preferably run in O(n) time and use only O(1) memory.
參考：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
if(NULL == headA || NULL == headB){
return NULL;
}
int i, n1, n2;
n1 = n2 = 1;
struct ListNode *p1, *p2;
p1 = headA, p2 = headB;
while(p1->next){
n1++;
p1 = p1->next;
}
while(p2->next){
n2++;
p2 = p2->next;
}
if(p1 != p2){
return NULL;
}
p1 = headA, p2 = headB;
if(n1 >= n2){
for(i = 0; i < n1 - n2; i++){
p1 = p1->next;
}
}
else{
for(i = 0; i < n2 - n1; i++){
p2 = p2->next;
}
}
while(p1 != p2){
p1 = p1->next;
p2 = p2->next;
}
return p1;
}
Sort a linked list using insertion sort.
參考：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
void swap(int *a, int *b){
int t = *a;
*a = *b;
*b = t;
}
struct ListNode* insertionSortList(struct ListNode* head) {
if(NULL == head || NULL == head->next){
return head;
}
int i, j, n = 0;
struct ListNode *p = head;
while(p){
n++;
p = p->next;
}
int *nums = (int*)malloc(sizeof(int)*n);
p = head;
i = 0;
while(p){
nums[i++] = p->val;
p = p->next;
}
//insertion sort
for(i = 1; i < n; i++){
j = i;
while(j && nums[j] < nums[j - 1]){
swap(nums + j, nums + j - 1);
j--;
}
}
p = head;
i = 0;
while(p){
p->val = nums[i];
p = p->next;
i++;
}
free(nums);
return head;
}
Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.
Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.
參考：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
void deleteNode(ListNode* node) {
if(node){
ListNode *p1, *p2;
p1 = node, p2 = node->next;
while(p2->next){
p1->val = p2->val;
p1 = p2;
p2 = p2->next;
}
p1->val = p2->val;
delete p2;
p1->next = NULL;
}
}
};
You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
參考：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
if(NULL == l1) return l2;
if(NULL == l2) return l1;
struct ListNode *head = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode *p1, *p2, *p;
p1 = l1, p2 = l2, p = head;
int more = 0; //more表示進位值
p->val = (p1->val + p2->val) % 10;
more = (p1->val + p2->val) / 10;
p1 = p1->next, p2 = p2->next;
while(p1 && p2)
{
p->next = (struct ListNode*)malloc(sizeof(struct ListNode));
p = p->next;
p->val = (p1->val + p2->val + more) % 10;
more = (p1->val + p2->val + more) / 10;
p1 = p1->next, p2 = p2->next;
}
while(p1)
{
p->next = (struct ListNode*)malloc(sizeof(struct ListNode));
p = p->next;
p->val = (p1->val + more) % 10;
more = (p1->val + more) / 10;
p1 = p1->next;
}
while(p2)
{
p->next = (struct ListNode*)malloc(sizeof(struct ListNode));
p = p->next;
p->val = (p2->val + more) % 10;
more = (p2->val + more) / 10;
p2 = p2->next;
}
if(more)//仍有進位
{
p->next = (struct ListNode*)malloc(sizeof(struct ListNode));
p = p->next;
p->val = more;
}
p->next = NULL;
return head;
}
