Algorithm

题目： A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. Return a deep copy of the list. Example 1: Input: {"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1} Explanation: Node 1's value is 1, both of its next and random pointer points to Node 2. Node 2's value is 2, its next pointer points to null and its random pointer points to itself. Note: ...

题目： You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure, as shown in the example below. Flatten the list so that all the nodes appear in a single-level, doubly linked list. You are given the head of the first level of the list. ...

题目： 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. Example: Input: 1->2->4, 1->3->4 Output: 1->1->2->3->4->4 解题： 新申请哨兵节点重组新的链表返回 。 比较两个链表选择较小的接入新链表，对于较长的链表，将其剩余部分接到新链表的尾部。 实现： struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){ struct ListNode* result = (struct ListNode *)malloc(sizeof(struct ListNode) ); if (result == NULL){ return NULL; } result->next = NULL; struct ListNode* l3 = result; while(l1!=NULL && l2!=NULL){ if (l1->val<l2->val){ l3->next = l1; l1= l1->next; l3= l3->next; }else{ l3->next = l2; l2= l2->next; l3= l3->next; } } if (l1!=NULL){ l3->next = l1; } else if (l2!=NULL){ l3->next = l2; } return result->next; } 递归方式：比较两个链表当前节点较小节点，这个结点的next节点与另外一个链表的当前节点比较，更新next节点。终止条件，如果一个节点为空，则返回另外一个节点。 ...

题目： You are given two non-empty linked lists representing two non-negative integers. 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. You may assume the two numbers do not contain any leading zero, except the number 0 itself. Example: Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 Explanation: 342 + 465 = 807. 解题： 生成结果链表哨兵节点， 从输入两个链表的开始节点相加 再加上进位值 carry， 得到结果sum， sum/10 存放到变量进位结果变量carry中， 将sum%/10为当前位的值，存放到链表当前节点，同时两个输入链表，结果链表移动到下一个节点操作。 循环处理直到链表遍历完毕或者进位为0，返回哨兵节点的下一个节点。 ...

Photo by Tim Swaan on Unsplash 题目： Design your implementation of the linked list. You can choose to use the singly linked list or the doubly linked list. A node in a singly linked list should have two attributes: val and next. val is the value of the current node, and next is a pointer/reference to the next node. If you want to use the doubly linked list, you will need one more attribute prev to indicate the previous node in the linked list. Assume all nodes in the linked list are 0-indexed. ...

Given a singly linked list, determine if it is a palindrome. Example 1: Input: 1->2 Output: false Example 2: Input: 1->2->2->1 Output: true Follow up: Could you do it in O(n) time and O(1) space? 解题： 找到中间节点后反转判断节点回文 实现： /** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ bool isPalindrome(struct ListNode* head){ if (head == NULL || head->next == NULL) { return true; } struct ListNode* slow=head; struct ListNode* fast=head; struct ListNode* pre=NULL; struct ListNode* next=NULL; //get middle while( fast!=NULL && fast->next!=NULL){ slow = slow->next; fast = fast->next->next; } if(fast) { slow=slow->next; } struct ListNode* cur=slow; //and reverse while(cur!=NULL){ pre = cur; cur = cur->next; pre->next = next; next = pre; } //compare cur = head; while(pre!=NULL){ //printf("%d %d\n", head->val, pre->val); if (cur->val != pre->val){ return false; } cur=cur->next; pre= pre->next; } return true; }

题目： Given an array of integers nums, write a method that returns the “pivot” index of this array. We define the pivot index as the index where the sum of the numbers to the left of the index is equal to the sum of the numbers to the right of the index. If no such index exists, we should return -1. If there are multiple pivot indexes, you should return the left-most pivot index. ...