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

题目： 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 解题： 新申请哨兵节点重组新的链表返回 。 比较两个链表选择较小的接入新链表，对于较长的链表，将其剩余部分接到新链表的尾部。 实现： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 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

Photo by Tim Swaan on Unsplash

Given a singly linked list, determine if it is a palindrome. Example 1: 1 2 Input: 1->2 Output: false Example 2: 1 2 Input: 1->2->2->1 Output: true Follow up: Could you do it in O(n) time and O(1) space? 解题： 找到中间节点后反转判断节点回文 实现： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 /** * 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. ...