输出链表最后几个第k个结点PHP已毕,链表中倒数第k个结点

输入三个链表,输出该链表中尾数第k个结点。第一个指针走(k-1)步,到达第k个节点,五个指针同时今后运动,当首个结点到达最终的时候,第四个结点所在地方就是尾数第k个节点了

  • 1判断三个单链表是不是有环
  • 2判定三个单链表中环的进口
  • 输出链表最后几个第k个结点PHP已毕,链表中倒数第k个结点。3在链表的第k个位置插入三个结点
  • 4找到链表中的尾数第k个职分的结点
  • 5链表逆置
  • 6删除值为n的结点
  • 7合并有序链表

链表中倒数第k个结点

题目:
输入多个链表,输出该链表中倒数第k个结点。

<?php
class Node{
        public $data;
        public $next;
}
//创建一个链表
$linkList=new Node();
$linkList->next=null;
$temp=$linkList;
for($i=1;$i<=10;$i++){
        $node=new Node();
        $node->data="aaa{$i}";
        $node->next=null;
        $temp->next=$node;
        $temp=$node;
}
//输入一个链表,输出该链表中倒数第k个结点。

function find($linkList,$k){
        //速度快的指针
        $fast=$linkList;
        //速度慢的指针
        $slow=$linkList;
        //快指针先移动k-1步
        for($i=0;$i<$k-1;$i++){
                $fast=$fast->next;
        }   
        if($fast->next==null){
                return false;
        }   
        //快慢指针一块移动
        while($fast->next!=null){
                $fast=$fast->next;
                $slow=$slow->next;
        }   
        return $slow;
}


$knode=find($linkList,2);
var_dump($knode);

object(Node)#10 (2) {
  ["data"]=>
  string(4) "aaa9"
  ["next"]=>
  object(Node)#11 (2) {
    ["data"]=>
    string(5) "aaa10"
    ["next"]=>
    NULL
  }
}

标题叙述

  输入三个链表,输出该链表中尾数第k个结点。


解法
分析:
常规解法:首先遍历一次拿到链表节点个数n,然后初叶走n-k步即到达倒数第k个节点
日子复杂度O(n+n-k)
遍历四遍的做法:
设多个指针同时针对表头,第两个指针先走k步,此时七个指针的偏离为k,那么七个指针同时今后走,当首个指针到达链表结尾时,另三个指南针即指向了尾数第k个结点

 

  • [① 、判断二个单链表是还是不是有环]
    可利用一快一慢八个指针,贰个指南针每一遍走一步,另三个指南针一遍走两步。若存在环,若干步后,快的指针会赶上慢的指针。否则则判定不存在环

思路

  1. 美高梅开户网址 ,七个指针,先让第二个指针和第一个指针都针对头结点,然后再让第一个指正走(k-1)步,到达第k个节点;
  2. 然后多个指针同时未来移动,当第一个结点到达最后的时候,首个结点所在地点就是尾数第k个节点了。
  3. 大旨考察鲁棒性,因而要看清空值和负值以及k值不大概超过链表的长度。
  4. 宗旨链表不含头结点。

百发百中代码

// Node用来标识结点,element用来保存节点上的数据,next用来保存指向下一个节点的链接
function Node(element) {
    this.element = element;
    this.next = null;
}

/* 在Node的原型链上添加insert方法,
判断链表是否为空,若为空,则在添加第一个结点,
若不为空,则在当前结点后面添加新的结点。*/
Node.prototype.insert = function(newElement) {
    if (this.element === undefined) {
        this.element = newElement;
    } else {
        var curNode = this;
        while (curNode.next !== null) {
            curNode = curNode.next;
        }
        var newNode = new Node(newElement);
        curNode.next = newNode;
        newNode.next = null;
    }
};

// 查找链表中倒数第k个结点
function FindKthToTail(head, k) {
    if (head.element === undefined) {
        return new Error("head为空链表!");
    }
    if (k <= 0) {
        return new Error("k小于等于0!");
    }
    var pre = head;
    var last = head;
    for (var i = 1; i < k; i++) {
        if (pre.next !== null) {
            pre = pre.next;
        } else {
            return new Error("k值过大!");
        }
    }
    while (pre.next !== null) {
        pre = pre.next;
        last = last.next;
    }
    return last;
}

var node = new Node(); 
node.insert("Kobe");
node.insert("Curry");
node.insert("Russel");
node.insert("Klay");
node.insert("Tracy");
console.log(node);
var empty = {};
public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}
static ListNode hasCircle(ListNode node) {
        if (node == null)
            return null;
        ListNode resultNode = null;
        ListNode slow = node.next;
        if (slow == null)
            return null;
        ListNode fast = slow.next;
        while (fast != null && slow != null) {
            if (fast == slow) {
                resultNode = fast;
                break;
            }
            slow = slow.next;
            fast = fast.next;
            if (fast != null) {
                fast = fast.next;
            }
        }
        return resultNode ;
    }

举例

FindKthToTail(node, -2);

美高梅开户网址 1
FindKthToTail(empty , 2);

美高梅开户网址 2
FindKthToTail(node, 100);

美高梅开户网址 3

FindKthToTail(node, 2);

美高梅开户网址 4

  • [2判定3个单链表中环的输入节点]
    率先应用1中艺术判断链表中是或不是有环,获取环中任意贰个节点,然后拿走环的长短为n。
    下一场定义三个指针,三个指针先走n步,然后三个指针在以同一的进程移动,当第三个指针走到进口节点时,第1个指针刚好走了一圈,也抵达入口节点,那时就找到了环的输入节点。

static ListNode getEntryNode(ListNode node) {
        ListNode meetingNode = hasCircle(node);
        if (meetingNode == null)
            return null;
        int loopNum = 1;
        ListNode pNode1 = meetingNode;
        while (pNode1.next != meetingNode) {
            pNode1 = pNode1.next;
            ++loopNum;
        }
        pNode1 = node;
        for (int i = 0; i < loopNum; i++) {
            pNode1 = pNode1.next;
        }
        ListNode pNode2 = node;
        while (pNode1 != pNode2) {
            pNode1 = pNode1.next;
            pNode2 = pNode2.next;
        }
        return pNode1;
    }
  • 3在链表的第k个职位插入一个结点
    若链表为空,则一贯将插入数据作为第多个结点;
    若插入第1个岗位和插入最终2个义务,都要考虑到。

      //返回头指针
    static ListNode insertNode(ListNode node, int k, int num) {
        ListNode kNode = new ListNode(num);
        if (node == null)
            node = new ListNode(num);
        int i = 0;
        ListNode preNode = node;
        while (preNode != null && i < k - 1) {
            if (++i == k - 1)
                break;
            preNode = preNode.next;
        }
        if ((k - 1) != i) {// 插入位置不合法
            return node;
        }
        if (k == 1) {// 插入首位
            kNode.next = node;
            node = kNode;
        } else {
            // 中间节点或尾结点
            kNode.next = preNode.next;
            preNode.next = kNode;
        }
        return node;
    }
  • 4找到单链表中的倒数第k个岗位的结点
    设链表长为n,从后往前查第k个结点即此前将来找的第n-k+3个结点。那时能够动用几个指针,第柒个指针先走k-1步,第k步时,八个指针同时往前走,因为多少个指针始终相差k-1,所以当第二个指针到达链表终点时,第三个指针刚好到达n-k+贰个结点,即尾数第k个结点。

    static ListNode getKNode(ListNode node, int k) {
        ListNode pHead = node;
        ListNode pBehind = null;
        for (int i = 0; i < k - 1; i++) {
            pHead = pHead.next;
        }
        while (pHead.next != null) {
            pHead = pHead.next;
            pBehind = pBehind.next;
        }
        return pBehind;
    }
  • 5链表逆置

public static ListNode reverseNode(ListNode node) {
        if (node == null)
            return null;
        ListNode reverseNode = null;
        ListNode head = node;
        ListNode preNode = null;
        while (head != null) {
            ListNode nextNode = head.next;
            if (nextNode == null)
                reverseNode = head;
            head.next = preNode;
            preNode = head;
            head = nextNode;
        }
        return reverseNode;
    }
  • 6删除值为n的结点

public static ListNode delete(ListNode node, int data) {
        if (node == null)
            return null;
                //现将链表头部的值为data的数据删除
        while (node != null) {
            if (node.val == data)
                node = node.next;
            else   break;
        }
        ListNode preNode = null;//要删除的节点的前一个结点
        ListNode temp = node;//返回链表,先指向头结点
        ListNode head = node;//遍历指针
        while (head != null) {
            if (head.val != data) {
                preNode = head;
            } else {
                preNode.next = preNode.next.next;
            }
                        head = head.next;
        }
        return temp;
    }

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图