咸糖记录编程的地方

念念不忘,必有回响。

目录
数据结构 1.链表 一图胜千言
/  

数据结构 1.链表 一图胜千言

92. Reverse Linked List II

Reverse a linked list from position m to n. Do it in one-pass.

Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

代码:


class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
    if(head == null) {
        return null;
    }
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode pre = dummy;
    for(int i = 0 ; i<m-1;i++){
        pre = pre.next;
    }
    ListNode start = pre.next;
    ListNode then = start.next;
    for(int j = 0;j<n-m;j++){
        start.next = then.next;
        then.next = pre.next;
        pre.next = then;
        then = start.next;
    }
    return dummy.next;
    }
}

206. Reverse Linked List

Reverse a singly linked list.


Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

class Solution {
    public ListNode reverseList(ListNode head) {
        
        ListNode pre = null;
        ListNode curr = head;
        while(curr != null){
            ListNode next_temp = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next_temp;
        }
        return pre;
    }
}

24. Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.
You may not modify the values in the list’s nodes, only nodes itself may be changed.

Given 1->2->3->4, you should return the list as 2->1->4->3.

为什么要使用dummy:

  • head 位置会跳到第二个位置
class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode cur = dummy;
        while(cur.next!=null && cur.next.next!=null){
            ListNode first = cur.next;
            ListNode second = cur.next.next;
            first.next = second.next;
            second.next =first;
            cur.next = second;
            cur = first;
        }
        return dummy.next;
    }
}

142. Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null. To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

  • 定义快慢指针判断是否是环
  • 如果是环,就将 slow 指针移到开头,保持 fast 指针的位置
  • 两个指针每次只走一步,这一次的交点就是环的入口

道理我都懂但是为什么呢?? 为什么要放到开头呢?? 下面我给出我的数学证明!

首先定义

  • 链表入环口为 d
  • 链表头的位置是 h
  • 快慢指针初次相遇的位置为 c
  • 链表的总长度为 L
  • 链表头到入环口的长度为 A
  • 入环口到快慢指针初次相遇的位置的长度是 X
  • 环的长度是 R

首先可以确定在相遇的时候快指针可能在里面转了n圈
并且慢指针并没有走完一圈
并且快慢指针具有一个性质,快指针永远是慢指针速度的两倍
我们设定头节点 h 到快慢指针初次相遇的位置 c 的位置的长度为 S

我们可以推断出一下等式:

n*R + S = 2*S
//  等式前面是快指针走的长度,后面是两倍的慢指针走的长度
n*R = S

又因为 S 的长度是 A 和 X 的和

S = X+A

结合两个等式可以推断出

A + X = n*R
A + X = (n-1)R +  (L-A)
A = (n-1)R + (L-A-X)  // L-A 就是环的长度R

那么 R-X 的长度就是 c到d 的长度

令 slow 从头节点 点出发,fast 从c 出发,每次移动 1 就可以到达入环口 d。


public class Solution {
    public ListNode detectCycle(ListNode head) {
        
        ListNode fast = head;
        ListNode slow = head;
        boolean isCycle = false;
        while(fast!=null && fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                isCycle = true;
            }
        }
        if(isCycle){
            slow = head;
            while(true){
                slow = slow.next;
                fast = fast.next;
                if(slow == fast){
                    return slow;
                }
            }
        }
        else return null;
    }
}



标题:数据结构 1.链表 一图胜千言
作者:xiantang
地址:http://xiantang.info/articles/2019/06/03/1559551212779.html

评论