在线教育网站开发实例网站建设技术服务方案

当前位置： 首页 > news >正文

在线教育网站开发实例,网站建设技术服务方案,织梦网站首页文章,互联网公司的最新排名【算法】009、单双链表反转 文章目录 一、单链表反转1.1 实现思路1.2 多语言解法 二、双链表反转2.1 实现思路2.2 多语言解法 一、单链表反转 1.1 实现思路 维护 pre 变量。 从前向后遍历 head#xff0c;首先记录 next head.next#xff0c;其次反转指针使 head.next pr…【算法】009、单双链表反转 文章目录 一、单链表反转1.1 实现思路1.2 多语言解法 二、双链表反转2.1 实现思路2.2 多语言解法 一、单链表反转 1.1 实现思路 维护 pre 变量。 从前向后遍历 head首先记录 next head.next其次反转指针使 head.next pre. 再向后迭代使 pre headhead next。 直到遍历完 head nil 为止。最终 pre 就是原链表的尾节点即新链表的头节点返回 pre 即可。 // go package mainimport fmt// single type Node struct {val intnext *Node }func main() {la : la()laCheck(reverse(la))lb : lb()if reverse(lb) ! lb {panic(error for lb)}lnil : lnil()if reverse(lnil) ! nil {panic(error for nil)}print(ok) }func la() *Node {a : Node{val: 0}b : Node{val: 1}c : Node{val: 2}a.next bb.next creturn a }func laCheck(h *Node) error {ans : make([]int, 0)for iter : h; iter ! nil; iter iter.next {ans append(ans, iter.val)}if len(ans) ! 3 {return fmt.Errorf(err len)}if ans[0] ! 3 {return fmt.Errorf(err val)}if ans[1] ! 1 {return fmt.Errorf(err val)}if ans[2] ! 0 {return fmt.Errorf(err val)}return nil }func lb() *Node {return Node{val: 5, next: nil} }func lnil() *Node {var n *Node nilreturn n }func reverse(head *Node) *Node {if head nil {return nil}var pre *Node nilvar next *Node nilfor head ! nil {next head.next // 备份 head.next, 因为下一行就要改其指向了head.next pre // 反转的关键, 指针方向变了, 原来 head.next 指向 next, 现在 head.next 指向 prepre head // 向后迭代head next // 同上}return pre }1.2 多语言解法 C p p / G o / P y t h o n / R u s t / J s / T s Cpp/Go/Python/Rust/Js/Ts Cpp/Go/Python/Rust/Js/Ts // cpp #include iostream #include vector #include algorithmusing namespace std; struct Node {int val;Node *next; };Node *la() {Node *c new Node{2, nullptr};Node *b new Node{1, c};Node *a new Node{0, b};return a; }void laCheck(Node *head) {vectorint ans;Node *iter head;while (iter ! nullptr){ans.push_back(iter-val);iter iter-next;}if (ans.size() ! 3){throw runtime_error(length error);}if (ans[0] ! 2){throw runtime_error(0 error);}if (ans[1] ! 1){throw runtime_error(1 error);}if (ans[2] ! 0){throw runtime_error(2 error);} }Node *lb() {return new Node{5, nullptr}; }void lbCheck(Node *head) {vectorint ans;Node *iter head;while (iter){ans.push_back(iter-val);iter iter-next;}if (ans.size() ! 1){throw runtime_error(length error);}if (ans[0] ! 5){throw runtime_error(5 error);} }Node *lnone() {return nullptr; }Node *reverse(Node *head) {Node *pre nullptr;Node *iter head;while (iter){Node *next iter-next;iter-next pre;pre iter;iter next;}return pre; }int main() {Node *l la();Node *r reverse(l);laCheck®;l lb();r reverse(l);lbCheck®;l lnone();r reverse(l);if (r ! nullptr){throw runtime_error(error for lnone);}cout ok endl; }// go 同上# python class Node(object):def init(self, v, n):self.val vself.next ndef la():c Node(2, None)b Node(1, c)a Node(0, b)return adef laCheck(n):ans []while n:ans.append(n.val)n n.nextif ans ! [2, 1, 0]:raise ValueErrordef lb():return Node(5, None)def reverse(head):pre Nonenext Nonewhile head:next head.nexthead.next prepre headhead nextreturn predef main():l la()l reverse(l)laCheck(l)l lb()if reverse(l) ! l:raise ValueError(123)if reverse(None) ! None:raise ValueError(111)print(ok)if name main:main()// rust fn main() {let l la();let r reverse(l);la_check®.expect(la_check);let l lb();let r reverse(l);lb_check®.expect(lb_check);let l lnone();let r reverse(l);if r.is_some() {panic!(lnone);}println!(ok) }#[derive(Debug)] struct Node {val: i32,next: OptionBoxNode, }impl Node {fn new(val: i32, next: OptionBoxNode) - Self {Self { val, next }} }fn la() - OptionBoxNode {let c Some(Box::new(Node::new(2, None)));let b Some(Box::new(Node::new(1, c)));let a Some(Box::new(Node::new(0, b)));a }fn la_check(head: OptionBoxNode) - Result(), String {let mut ans vec![];let mut iter head;while let Some(node) iter {ans.push(node.val);iter node.next;}if ans.len() ! 3 {return Err(len.to_string());}if ans[0] ! 2 {return Err(0.to_string());}if ans[1] ! 1 {return Err(1.to_string());}if ans[2] ! 0 {return Err(2.to_string());}Ok(()) }fn lb() - OptionBoxNode {Some(Box::new(Node::new(5, None))) }fn lb_check(head: OptionBoxNode) - Result(), String {let mut ans vec![];let mut head head;while let Some(node) head {ans.push(node.val);head node.next;}if ans.len() ! 1 {return Err(len.to_string());}if ans[0] ! 5 {return Err(5.to_string());}Ok(()) }fn lnone() - OptionBoxNode {None }fn reverse(head: OptionBoxNode) - OptionBoxNode {let mut head head;let mut pre: OptionBoxNode None;while let Some(mut node) head {let next node.next.take();node.next pre;pre Some(node);head next;}pre }// js// ts function main() {let l la();let r reverse(l);laCheck®;l lb();r reverse(l);lbCheck®;l lnone();r reverse(l);if ® {throw new Error(lnone);}console.log(ok); }class ListNode {val: number;next: ListNode | null;constructor(val: number, next: ListNode | null) {this.val val;this.next next;} }function la(): ListNode | null {const c new ListNode(2, null);const b new ListNode(1, c);const a new ListNode(0, b);return a; }function laCheck(head: ListNode | null) {const ans: number[] [];let iter: ListNode | null head;while (iter) {ans.push(iter.val);iter iter.next;}if (ans.length ! 3) {throw new Error(length);}if (ans[0] ! 2) {throw new Error(0)}if (ans[1] ! 1) {throw new Error(1);}if (ans[2] ! 0) {throw new Error(2);} }function lb(): ListNode {return new ListNode(5, null); }function lbCheck(head: ListNode | null) {const ans: number[] [];let iter: ListNode | null head;while (iter) {ans.push(iter.val);iter iter.next;}if (ans.length ! 1) {throw new Error(length);}if (ans[0] ! 5) {throw new Error(5);} }function lnone(): ListNode | null {return null; }function reverse(head: ListNode | null): ListNode | null {let pre: ListNode | null null;while (head) {const next head.next;head.next pre;pre head;head next;}return pre; }main();二、双链表反转 2.1 实现思路 和 单链表反转 相同每次反转两个指针即可即 head.next pre 和 head.pre next。 package mainfunc main() {l : la()r : reverse(l)laCheck®l lb()r reverse(l)lbCheck®r reverse(nil)if r ! nil {panic(lnil)}println(ok) }type Node struct {val intpre *Nodenext *Node }func la() *Node {c : Node{2, nil, nil}b : Node{1, nil, c}a : Node{0, nil, b}c.pre bb.pre areturn a }func laCheck(h *Node) {ans : []int{}iter : hfor iter ! nil {ans append(ans, iter.val)iter iter.next}if len(ans) ! 3 {panic(length is not 3)}if ans[0] ! 2 {panic(0 is not the first element)}if ans[1] ! 1 {panic(1 is not the second element)}if ans[2] ! 0 {panic(2 is not the third element)} } func lbCheck(h *Node) {ans : []int{}iter : hfor iter ! nil {ans append(ans, iter.val)iter iter.next}if len(ans) ! 1 {panic(length is not 3)}if ans[0] ! 5 {panic(0 is not the first element)} }func lb() *Node {return Node{5, nil, nil} }func reverse(h *Node) *Node {var pre *Node niliter : hfor iter ! nil {next : iter.nextiter.next preiter.pre nextpre iteriter next}return pre }2.2 多语言解法 C p p / G o / P y t h o n / R u s t / J s / T s Cpp/Go/Python/Rust/Js/Ts Cpp/Go/Python/Rust/Js/Ts #include iostream #include algorithm #include vector using namespace std;class Node { public:int val;Node *pre;Node *next;Node() : val(0), pre(nullptr), next(nullptr) {}Node(int val) : val(val), pre(nullptr), next(nullptr) {}Node(int val, Node *pre, Node *next) : val(val), pre(pre), next(next) {} };Node *la() {Node *c new Node(2);Node *b new Node(1);Node *a new Node(0);a-next b;b-next c;c-pre b;b-pre a;return a; }void la_check(Node *h) {vectorint ans;Node *iter h;while (iter){ans.push_back(iter-val);iter iter-next;}if (ans.size() ! 3){throw new runtime_error(size);}if (ans[0] ! 2){throw new runtime_error(0);}if (ans[1] ! 1){throw new runtime_error(1);}if (ans[2] ! 0){throw new runtime_error(2);} }Node *lb() {return new Node(5); }void lb_check(Node *h) {if (h nullptr){throw new runtime_error(h null);}if (h-val ! 5){throw new runtime_error(val);} }Node *reverse(Node *h) {Node *pre nullptr;Node *iter h;while (iter){Node *next iter-next;iter-next pre;iter-pre next;pre iter;iter next;}return pre; }int main() {Node *l la();Node *r reverse(l);la_check®;Node *l2 lb();Node *rb reverse(l2);lb_check(rb);Node *lnull nullptr;if (reverse(nullptr)){throw new runtime_error(lnull);}cout ok endl; }# python def main():l la()r reverse(l)la_check®l lb()r reverse(l)lb_check®l Noner reverse(l)if r is not None:raise Exception(error)print(ok)class Node(object):def init(self, val):self.val valself.pre Noneself.next Nonedef la():cNode(2)bNode(1)aNode(0)a.next bb.next cc.pre bb.pre areturn adef la_check(h):ans []cur hwhile cur:ans.append(cur.val)cur cur.nextif ans ! [2,1,0]:raise Exception(error)def lb():return Node(5)def lb_check(h):if h.val ! 5:raise Exception(error)if h.next is not None:raise Exception(error)if h.pre ! None:raise Exception(error)def reverse(h):pre Nonecur hwhile cur:next cur.nextcur.next precur.pre nextpre curcur nextreturn preif name main:main()// rust use std::cell::RefCell; use std::rc::Rc;#[derive(Debug)] struct Node {val: i32,prev: OptionRcRefCellNode,next: OptionRcRefCellNode, }impl Node {fn new(val: i32) - Self {Node {val,prev: None,next: None,}} }fn la() - OptionRcRefCellNode {let c Rc::new(RefCell::new(Node::new(2)));let b Rc::new(RefCell::new(Node::new(1)));let a Rc::new(RefCell::new(Node::new(0)));a.borrow_mut().next Some(b.clone());b.borrow_mut().next Some(c.clone());c.borrow_mut().prev Some(b.clone());b.borrow_mut().prev Some(a.clone());Some(a) }fn la_check(h: OptionRcRefCellNode) {let mut iter h;let mut ans Vec::new();while let Some(node) iter {ans.push(node.borrow().val);iter node.borrow().next.clone();}if ans.len() ! 3 {panic!(length is not 3);}if ans[0] ! 2 {panic!(0 error);}if ans[1] ! 1 {panic!(1 error);}if ans[2] ! 0 {panic!(2 error);} }fn lb() - OptionRcRefCellNode {Some(Rc::new(RefCell::new(Node::new(5)))) }fn lb_check(h: OptionRcRefCellNode) {let mut iter h;let mut ans Vec::new();while let Some(node) iter {ans.push(node.borrow().val);iter node.borrow().next.clone();}if ans.len() ! 1 {panic!(length is not 1);}if ans[0] ! 5 {panic!(0 error);} }fn reverse(h: OptionRcRefCellNode) - OptionRcRefCellNode {let mut cur h;let mut pre: OptionRcRefCellNode None;while let Some(node) cur {let next node.borrow_mut().next.take();node.borrow_mut().next pre;node.borrow_mut().prev next.clone();pre Some(node);cur next}pre }fn main() {let l la();let r reverse(l);la_check®;let l lb();let r reverse(l);lb_check®;let l: OptionRcRefCellNode None;let r reverse(l);if r.is_some() {panic!(r is not None);}println!(ok); }function main() {let l la();let r reverse(l);la_check®;l lb();r reverse(l);lb_check®;r reverse(null);if ® {throw new Error(lnull error)}console.log(ok) }class ListNode {val: number;prev: ListNode | null;next: ListNode | null;constructor(val: number) {this.val val;this.prev null;this.next null;} }function la(): ListNode | null {const c new ListNode(2);const b new ListNode(1);const a new ListNode(0);a.next b;b.next c;c.prev b;b.prev a;return a; }function la_check(h: ListNode | null) {let ans: number[] [];let iter: ListNode | null hwhile (iter) {ans.push(iter.val);iter iter.next;}if (ans.length ! 3) {throw new Error(length error)}if (ans[0] ! 2) {throw new Error(0 error)}if (ans[1] ! 1) {throw new Error(1 error)}if (ans[2] ! 0) {throw new Error(2 error)} }function lb(): ListNode | null {return new ListNode(5); }function lb_check(h: ListNode | null) {if (!h) {throw new Error(h null error)}if (h.val ! 5) {throw new Error(5 error)}if (h.next) {throw new Error(next error)}if (h.prev) {throw new Error(prev error)} }function reverse(h: ListNode | null): ListNode | null {let iter: ListNode | null h;let prev: ListNode | null null;while (iter) {let next iter.next;iter.next prev;iter.prev next;prev iteriter next}return prev }main();