鏈表實(shí)現(xiàn)
LinkNode.h文件 鏈表類 .m文件什么都不用寫
@interface LinkNode : NSObject
@property (nonatomic, assign) int val;
@property (nonatomic, strong, nullable) LinkNode *next;
@end
鏈表實(shí)現(xiàn)
+ (LinkNode*)arrayTransforLink:(NSArray *)array{
LinkNode *node = [LinkNode new],*p = [LinkNode new];
p.val = [array[0] intValue];
node.next = p;
for (int i = 1; i<array.count; i++) {
LinkNode *nextNode = [LinkNode new];
nextNode.val = [array[i] intValue];
p.next = nextNode;
p = p.next;
}
node = node.next;//刪除無用頭結(jié)點(diǎn)
return node;
}
//實(shí)現(xiàn)一個(gè)鏈表
LinkNode *node = [LinkTool arrayTransforLink:@[@1,@2,@3,@5]];
打印鏈表
+ (void)printNode:(LinkNode *)node{
while (node) {
NSLog(@"%d",node.val);
node = node.next;
}
}
鏈表反轉(zhuǎn) (使用遞歸法)
//反轉(zhuǎn)
+(LinkNode*)reversalLink:(LinkNode *)node{
LinkNode *p , *q, *t=node;
while (t) {
p = t;//淺拷貝
t = t.next;
p.next = q;
q = p;
}
return q;
}
兩個(gè)有序鏈表合并為一個(gè)有序鏈表
力扣題
將兩個(gè)升序鏈表合并為一個(gè)新的 升序 鏈表并返回机隙。新鏈表是通過拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的。
輸入：l1 = [1,2,4], l2 = [1,3,4]
輸出：[1,1,2,3,4,4]
+ (LinkNode*)merge:(LinkNode *)node link:(LinkNode*)link{
LinkNode *selfNode = link;
LinkNode *newNode = [LinkNode new];//記錄
LinkNode *headNode = newNode;//頭鏈表
while (selfNode&&node) {
if (selfNode.val < node.val) {
newNode.val = selfNode.val;
selfNode = selfNode.next;
}else{
newNode.val = node.val;
node = node.next;
}
newNode.next = [LinkNode new];
newNode = newNode.next;
}
LinkNode *p = selfNode?selfNode:node;
newNode.val = p.val;
return headNode;
}
鏈表 兩數(shù)相加 （簡(jiǎn)單的中等難度）
給你兩個(gè) 非空 的鏈表个绍，表示兩個(gè)非負(fù)的整數(shù)网棍。它們每位數(shù)字都是按照 逆序 的方式存儲(chǔ)的庶弃，并且每個(gè)節(jié)點(diǎn)只能存儲(chǔ) 一位 數(shù)字。
請(qǐng)你將兩個(gè)數(shù)相加，并以相同形式返回一個(gè)表示和的鏈表径荔。
你可以假設(shè)除了數(shù)字 0 之外垂寥，這兩個(gè)數(shù)都不會(huì)以 0 開頭颠黎。
實(shí)例一
輸入：l1 = [2,4,3], l2 = [5,6,4]
輸出：[7,0,8]
解釋：342 + 465 = 807.
實(shí)例二：
輸入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
輸出：[8,9,9,9,0,0,0,1]
思路：
- 遍歷兩個(gè)鏈表獲得兩個(gè)整數(shù)
- 兩個(gè)整數(shù)相加
- 獲得總數(shù)后整數(shù)轉(zhuǎn)鏈表
缺點(diǎn)：當(dāng)鏈表節(jié)點(diǎn)很多的時(shí)候會(huì)崩掉
如：
[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1]
[5,6,4]
// 整數(shù)轉(zhuǎn)鏈表
+ (LinkNode*)intTransforLink:(int)number{
LinkNode *node = [LinkNode new],*p = [LinkNode new];
node.next = p;
if (number<10) {
node.val = number;
return node;
}
while (number) {
int index = number%10;
LinkNode *nextNode = [LinkNode new];
nextNode.val = index;
p.next = nextNode;
p = p.next;
number = number/10;
}
node = node.next;//刪除無用頭結(jié)點(diǎn)
node = node.next;//刪除無用頭結(jié)點(diǎn)
return node;
}
//實(shí)現(xiàn)代碼
LinkNode *node = [LinkTool arrayTransforLink:@[@9,@9,@9,@9,@9,@9,@9]];
LinkNode *node1 = [LinkTool arrayTransforLink:@[@9,@9,@9,@9]];
double nodeValue = 0,node1Value = 0;
int times = 1;
while (node||node1) {
nodeValue = node.val*times + nodeValue;
node = node.next;
node1Value = node1.val*times + node1Value;
node1 = node1.next;
times*=10;
}
int totle = nodeValue + node1Value;
LinkNode *totleLink = [LinkTool intTransforLink:totle];
[LinkTool printNode:totleLink];
思路二：
- 遍歷每一個(gè)節(jié)點(diǎn)
- 兩個(gè)節(jié)點(diǎn)和進(jìn)位相加
- 是否超過10，超過則進(jìn)位1不超過則進(jìn)位0
- 子節(jié)點(diǎn)的創(chuàng)建依賴于兩個(gè)節(jié)點(diǎn)其中是否有子節(jié)點(diǎn)
- 每次判斷其中一個(gè)節(jié)點(diǎn)是否為空滞项。如果其中一個(gè)節(jié)點(diǎn)為空則判斷進(jìn)位是否為0 狭归，進(jìn)位為0則直接賦值不為空的節(jié)點(diǎn)
- 遍歷完后查看進(jìn)位是否為0 不為0則增加一個(gè)子節(jié)點(diǎn) 儲(chǔ)存進(jìn)位
+ (LinkNode*)addTwoNumbers:(LinkNode *)node link:(LinkNode *)node1{
LinkNode *totleNode = [LinkNode new],*p = [LinkNode new];
totleNode.next = p;
int number = 0;
while (node||node1) {
if (!node && number == 0) {
p.val = node1.val;
p.next = node1.next;
break;
}
if (!node1 && number == 0) {
p.val = node.val;
p.next = node.next;
break;
}
int totleValue = node.val+node1.val +number;
number = totleValue/10;
totleValue = totleValue%10;
p.val = totleValue;
node = node.next;
node1 = node1.next;
if (node||node1) {
p.next = [LinkNode new];
p = p.next;
}
}
if (number) {//判斷最后面是否有進(jìn)位
p.next = [LinkNode new];
p = p.next;
p.val = number;
}
totleNode = totleNode.next;//移除無用頭結(jié)點(diǎn)
return totleNode;
}
swift代碼
func addTwoNumbers(l1:LinkNode?,l2:LinkNode?) -> LinkNode {
var node1 = l1
var node2 = l2
var totleNode = LinkNode.init(),p = LinkNode.init()
totleNode.next = p
var number = 0
while ((node1 != nil)||(node2 != nil)) {
var totleValue = number
if node1 != nil {
totleValue = totleValue + node1!.val
}else if(number == 0){
p.val = node2!.val
p.next = node2?.next
break
}
if node2 != nil {
totleValue = totleValue + node2!.val
}else if(number == 0){
p.val = node1!.val
p.next = node1?.next
break
}
number = totleValue/10
totleValue = totleValue%10
p.val = totleValue
node1 = node1?.next
node2 = node2?.next
if ((node1 != nil)||(node2 != nil)) {
p.next = LinkNode.init()
p = p.next!
}
}
if number != 0 {
p.next = LinkNode.init()
p = p.next!
p.val = number
}
totleNode = totleNode.next!
return totleNode
}
