leetcode——链表

佚名 5年前 (2019-10-21) 算法 1351人围观抢沙发百度已收录

反转一个单链表。

示例:

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

c++:

/**
 * 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) {
        ListNode *newHead=NULL;
        while(head){
            ListNode *next=head->next;
            head->next=newHead;
            newHead=head;
            head=next;
        }
        return newHead;
    }
};

python:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        newHead=None
        while head!=None:
            nxt=head.next
            head.next=newHead
            newHead=head
            head=nxt
        return newHead

java:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode newHead=null;
        while(head!=null){
            ListNode next=head.next;
            head.next=newHead;
            newHead=head;
            head=next;
        }
        return newHead;
    }
}

92. 反转链表 II （中）
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
c++：

/**
 * 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) {
        ListNode* sta=head;
        int len=n-m+1;
        ListNode* pre=NULL;
        while(--m&&head){
            pre=head;
            head=head->next;
        }
        ListNode* e=head;
        ListNode* newHead=NULL;
        while(len--&&head){
            ListNode* next=head->next;
            head->next=newHead;
            newHead=head;
            head=next;
        }
        e->next=head;
        if(pre)
            pre->next=newHead;
        else 
            sta=newHead;
        return sta;
    }
};

python：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
        sta=head
        len = n-m+1
        pre=None
        while m!=1 and head!=None :
            pre=head
            m-=1
            head=head.next
        newHead=None
        ed=head
        while len!=0 and head!=None:
            nxt=head.next
            head.next=newHead
            newHead=head
            head=nxt
            len-=1
        ed.next=head
        if pre!=None:
            pre.next=newHead
        else :
            sta=newHead
        return sta

java：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        int len=n-m+1;
        ListNode pre=null,sta=head;
        while(--m!=0&&head!=null){
            pre=head;
            head=head.next;
        }
        ListNode ed=head,newHead=null,nxt=null;
        while(len--!=0&&head!=null){
            nxt=head.next;
            head.next=newHead;
            newHead=head;
            head=nxt;
        }
        ed.next=head;
        if(pre==null){
            return newHead;
        }else {
            pre.next=newHead;
            return sta;
        }
    }
}

160. 相交链表（易）

编写一个程序，找到两个单链表相交的起始节点。

如下面的两个链表：

在节点 c1 开始相交。
c++:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int a=0,b=0;
        ListNode *A=headA,*B=headB;
        while(A){
            a++;
            A=A->next;
        }
        while(B){
            b++;
            B=B->next;
        }
        if(a>b){
            int c=a-b;
            while(c--&&headA){
                headA=headA->next;
            }
            while(headA&&headB){
                if(headA==headB)
                    return headA;
                else 
                    headA=headA->next,headB=headB->next;
            }
        }else {
            int c=b-a;
            while(c--&&headB){
                headB=headB->next;
            }
            while(headA&&headB){
                if(headA==headB)
                    return headA;
                else 
                    headA=headA->next,headB=headB->next;
            }
        }
        return NULL;
    }
};

142. 环形链表 II（中）

给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。
说明：不允许修改给定的链表。
c++：
map直接搞：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        unordered_map<ListNode*,int> m;
        while(head){
            if(m[head]){
                return head;
            }
            m[head]=1;
            head=head->next;
        }
        return NULL;
    }
};

快慢指针：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *slow=head,*fast=head,*meet=NULL;
        while(slow&&fast){
            slow=slow->next;
            fast=fast->next;
            if(!fast){
                return NULL;
            }
            fast=fast->next;
            if(slow==fast){
          //      printf("%d %d",slow->val,fast->val);
        //        puts("gg");
                meet=slow;
                break;
            }
        }
   //     printf("hh");
        if(meet==NULL)
            return NULL;
   //     printf("hh");
        while(meet&&head){
            if(meet==head){
                return meet;
            }
            meet=meet->next;
            head=head->next;
        }
        return NULL;
    }
};

2. 两数相加（中）

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

思路：题意要理解清楚，模拟即可，很简单但要注意细节。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode t=new ListNode(0);
        ListNode cur=t;
        int pre=0;
        while(l1!=null||l2!=null){
            int x=(l1==null?0:l1.val);
            int y=(l2==null?0:l2.val);
            int sum=(x+y+pre);
            cur.next=new ListNode(sum%10);
            cur=cur.next;
            pre=sum/10;
            if(l1!=null)
                l1=l1.next;
            if(l2!=null)
                l2=l2.next;
        }
        if(pre!=0){
            cur.next=new ListNode(pre);
        }
        return t.next;
    }
}